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$, 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 it exists, is less than or equal to every element of the set.

The first line contains the number of test cases $T$ ($1 \le T \le 100$). Then $T$ test cases follow.

Each test case starts with 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.

The next $m$ lines each contain three integers $u$, $v$, $w$ ($0 \le u, v < n$, $0 \le w \le 9$), meaning there is an edge from $u$ to $v$ with weight $w$.

It is guaranteed that at least one path from node $0$ to node $1$ exists in each test case.

For each test case, output one line in the format "Case #x: y", where $x$ is the test case number starting from $1$. The value $y$ is the answer modulo $(10^9 + 7)$. Specifically, if the answer can be written as an irreducible fraction $\frac{A}{B}$, then $y$ is $(A \cdot B^{-1}) \bmod (10^9 + 7)$.

In the first test case, the path that achieves the infimum is $0 \to 2 \to 4 \to 1$, so the answer is $0.313$.