23440번 - Infimum of Paths 다국어

문제

On a directed graph, we use $lex(p)$ to denote the lexical weight of a path $p,ドル where the path $p$ can be regarded as a sequence of consecutive edges. The lexical weight is defined by the recurrence relation

$$lex([]) = 0, lex([e_1, e_2, \ldots, e_n]) = \frac{w(e_1) + lex([e_2, e_3, \ldots, e_n])}{10}\text{,}$$

where $w(e_1)$ is the weight of edge $e_1,ドル which is an integer between 0ドル$ and 9ドル,ドル inclusive.

Given a directed graph, find the infimum of the lexical weights of all paths from node 0ドル$ to node 1ドル$. The infimum of a set of rational numbers is the greatest rational number that, if exists, is less than or equal to all elements in this set.

입력

The first line of the input gives the number of test cases, $T$ (1ドル \le T \le 100$). $T$ test cases follow.

For each case, the first line contains two integers, $n$ (2ドル \le n \le 2000,ドル $\sum{n} \le 20000$) and $m$ (1ドル \le m \le 4000,ドル $\sum{m} \le 40000$), where $n$ is the number of nodes and $m$ is the number of edges.

Then $m$ lines follow, each of which contains three integers $u,ドル $v,ドル $w$ (0ドル \le u, v < n,ドル 0ドル \le w \le 9$), indicating an edge from $u$ to $v$ of weight $w$.

It is guaranteed that there exists at least one path from node 0ドル$ to node 1ドル$ for each test case.

출력

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1ドル$), and y is the answer modulo $(10^9 + 7)$. More specifically, if the answer can be formed as an irreducible fraction $\frac{A}{B},ドル then y will be $(A \cdot B^{-1}) \bmod (10^9 + 7)$.

제한

노트

For the first sample, the path corresponding to the infimum is 0ドル \to 2 \to 4 \to 1,ドル so the answer is 0ドル.313$.