경로의 하한

방향 그래프에서 경로 $p$의 사전식 가중치를 $lex(p)$로 나타낸다. 경로 $p$는 연속된 간선들의 수열로 볼 수 있다. 사전식 가중치는 다음 점화식으로 정의된다.

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

여기서 $w(e_1)$은 간선 $e_1$의 가중치이며, 0 이상 9 이하의 정수이다.

주어진 방향 그래프에서 노드 0에서 노드 1로 가는 모든 경로의 사전식 가중치에 대한 하한을 구하라. 유리수 집합의 하한은, 존재한다면, 그 집합의 모든 원소 이하인 가장 큰 유리수이다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 노드의 수 $n$ ($2 \le n \le 2000$, $\sum{n} \le 20000$)과 간선의 수 $m$ ($1 \le m \le 4000$, $\sum{m} \le 40000$)이 주어진다.

이어지는 $m$개의 줄에는 정수 $u$, $v$, $w$ ($0 \le u, v < n$, $0 \le w \le 9$)가 각각 주어진다. 이는 $u$에서 $v$로 가는 가중치 $w$의 간선을 뜻한다.

각 테스트 케이스에서 노드 0에서 노드 1로 가는 경로가 적어도 하나 존재함이 보장된다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이다. $y$는 답을 $(10^9 + 7)$로 나눈 나머지이다. 구체적으로, 답이 기약분수 $\frac{A}{B}$로 표현될 수 있다면 $y$는 $(A \cdot B^{-1}) \bmod (10^9 + 7)$이다.

첫 번째 테스트 케이스에서 하한을 이루는 경로는 $0 \to 2 \to 4 \to 1$이므로, 답은 $0.313$이다.