{"problem":{"name":"B. Infimum of Paths","description":{"content":"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 recurren","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10243B"},"statements":[{"statement_type":"Markdown","content":"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\n\n$$lex([]) = 0, lex([e_1, e_2, \\ldots, e_n]) = \\frac{w(e_1) + lex([e_2, e_3, \\ldots, e_n])}{10}\\text{,}$$\n\nwhere $w (e_1)$ is the weight of edge $e_1$, which is an integer between $0$ and $9$, inclusive.\n\nGiven 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.\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 100$). $T$ test cases follow.\n\nFor 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.\n\nThen $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$.\n\nIt is guaranteed that there exists at least one path from node $0$ to node $1$ for each test case.\n\nFor 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)$.\n\nFor 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$.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor 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)$.\n\n[samples]\n\n## Note\n\nFor 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$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ 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\\} $.  \nFor a path $ p = [e_1, e_2, \\dots, e_k] $, define its *lexical weight* recursively:  \n$$\n\\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}.\n$$\n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each test case:  \n   - $ 2 \\le n \\le 2000 $, $ \\sum n \\le 20000 $  \n   - $ 1 \\le m \\le 4000 $, $ \\sum m \\le 40000 $  \n   - Each edge $ (u, v, w) $ satisfies $ 0 \\le u, v < n $, $ 0 \\le w \\le 9 $  \n   - At least one path from node $ 0 $ to node $ 1 $ exists  \n\n**Objective**  \nFor 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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10243B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}