시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 256 MB111100.000%

## 문제

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)$.

## 예제 입력 1

2
5 5
0 2 3
2 3 4
2 4 1
3 1 2
4 1 3
5 6
0 1 9
2 0 6
3 0 1
0 3 3
4 0 3
4 2 7


## 예제 출력 1

Case #1: 241000002
Case #2: 40404041


## 노트

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