On a directed graph, we use $l e x (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 <= T <= 100$). $T$ test cases follow.
For each case, the first line contains two integers, $n$ ($2 <= n <= 2000$, $sum n <= 20000$) and $m$ ($1 <= m <= 4000$, $sum m <= 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 <= u, v < n$, $0 <= w <= 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 dot.op B^(-1)) bmod (10^9 + 7)$.
For the first sample, the path corresponding to the infimum is $0 arrow.r 2 arrow.r 4 arrow.r 1$, so the answer is $0. 313$.
## Input
The first line of the input gives the number of test cases, $T$ ($1 <= T <= 100$). $T$ test cases follow.For each case, the first line contains two integers, $n$ ($2 <= n <= 2000$, $sum n <= 20000$) and $m$ ($1 <= m <= 4000$, $sum m <= 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 <= u, v < n$, $0 <= w <= 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.
## Output
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 dot.op B^(-1)) bmod (10^9 + 7)$.
[samples]
## Note
For the first sample, the path corresponding to the infimum is $0 arrow.r 2 arrow.r 4 arrow.r 1$, so the answer is $0. 313$.
**Definitions**
Let $ G = (V, E) $ be a directed graph with $ V = \{0, 1, \dots, n-1\} $, $ E \subseteq V \times V $, and edge weights $ w: E \to \{0, 1, \dots, 9\} $.
For a path $ p = [e_1, e_2, \dots, e_k] $, define its *lexical weight* recursively:
$$
\mathrm{lex}([]) = 0, \quad \mathrm{lex}([e_1, e_2, \dots, e_k]) = \frac{w(e_1) + \mathrm{lex}([e_2, \dots, e_k])}{10}.
$$
**Constraints**
1. $ 1 \le T \le 100 $
2. For each test case:
- $ 2 \le n \le 2000 $, $ \sum n \le 20000 $
- $ 1 \le m \le 4000 $, $ \sum m \le 40000 $
- Each edge $ (u, v, w) $ satisfies $ 0 \le u, v < n $, $ 0 \le w \le 9 $
- At least one path from node $ 0 $ to node $ 1 $ exists
**Objective**
For each test case, compute the infimum of $ \mathrm{lex}(p) $ over all paths $ p $ from node $ 0 $ to node $ 1 $, and output it as $ A \cdot B^{-1} \mod (10^9 + 7) $, where $ \frac{A}{B} $ is the irreducible fraction representation of the infimum.