{"problem":{"name":"L. Lazy Mayor","description":{"content":"You have organized an event and for that you decorated the entire city, the City Mayor is the chief guest after all. You would like to show the Mayor around. But the Mayor is a picky person, he says h","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10088L"},"statements":[{"statement_type":"Markdown","content":"You have organized an event and for that you decorated the entire city, the City Mayor is the chief guest after all. You would like to show the Mayor around. But the Mayor is a picky person, he says he will travel exactly for K roads.\n\nThe City has N areas(numbered from 1 to N) and M undirected roads in total. You know the map and the fatigue value of each road, each pair of areas have at-most one road between them. You need to find for each pair of cities, what is the minimum fatigue value the Mayor will get if you show him around between that pair of cities, also you need to find out what are the number of ways in which the Mayor will get the minimum fatigue for that pair of city. Since the number of ways may be very large output it modulo (109 + 7).\n\nFirst line contains N, M and K(0 ≤ N ≤ 150,  and 0 ≤ K ≤ 109). Next M lines consists of description of all the roads; ith line has three integers u, v and w(1 ≤ u, v ≤ N and  - 106 ≤ w ≤ 106) which means that there is a direct path between area u and area v and has a fatigue value of w(the paths are undirected).\n\nOutput N lines, each containing 2 * N numbers. In the ith line, for each j(1 ≤ j ≤ N) output two integers: the minimum fatigue value if you start from i and go to j using exactly K roads; the number of ways to achieve that minimum fatigue value, modulo 109 + 7. If there is no path between i and j, using exactly K edges, output character  for fatigue value and 0 for number of ways.\n\nNote that there is no shortest path using one road from node i to node i, for all i.\n\nFor all other pair of nodes, there exist exactly one shortest path using one road. \n\n## Input\n\nFirst line contains N, M and K(0 ≤ N ≤ 150,  and 0 ≤ K ≤ 109). Next M lines consists of description of all the roads; ith line has three integers u, v and w(1 ≤ u, v ≤ N and  - 106 ≤ w ≤ 106) which means that there is a direct path between area u and area v and has a fatigue value of w(the paths are undirected).\n\n## Output\n\nOutput N lines, each containing 2 * N numbers. In the ith line, for each j(1 ≤ j ≤ N) output two integers: the minimum fatigue value if you start from i and go to j using exactly K roads; the number of ways to achieve that minimum fatigue value, modulo 109 + 7. If there is no path between i and j, using exactly K edges, output character  for fatigue value and 0 for number of ways.\n\n[samples]\n\n## Note\n\nNote that there is no shortest path using one road from node i to node i, for all i.For all other pair of nodes, there exist exactly one shortest path using one road.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M, K \\in \\mathbb{Z} $ with $ 0 \\leq N \\leq 150 $, $ 0 \\leq K \\leq 10^9 $.  \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{1, 2, \\dots, N\\} $ and $ E \\subseteq V \\times V $, $ |E| = M $.  \nEach edge $ (u, v) \\in E $ has a weight $ w(u, v) \\in \\mathbb{Z} $, $ -10^6 \\leq w(u, v) \\leq 10^6 $.  \nLet $ A \\in \\mathbb{Z}^{N \\times N} $ be the adjacency matrix where $ A_{u,v} = w(u,v) $ if $ (u,v) \\in E $, and $ A_{u,v} = \\infty $ otherwise (with $ A_{u,u} = \\infty $ for all $ u $).\n\n**Constraints**  \n1. $ 0 \\leq N \\leq 150 $, $ 0 \\leq K \\leq 10^9 $  \n2. Each pair of nodes has at most one edge.  \n3. Edge weights are integers in $ [-10^6, 10^6] $.  \n4. No self-loops: $ A_{u,u} = \\infty $ for all $ u $.  \n\n**Objective**  \nFor each ordered pair $ (i, j) \\in V \\times V $, compute:  \n- $ d_{i,j}^{(K)} $: the minimum total fatigue over all walks of exactly $ K $ edges from $ i $ to $ j $, or $ \\infty $ if no such walk exists.  \n- $ c_{i,j}^{(K)} $: the number of walks of exactly $ K $ edges from $ i $ to $ j $ achieving $ d_{i,j}^{(K)} $, modulo $ 10^9 + 7 $, or $ 0 $ if no such walk exists.  \n\nCompute and output for each $ i \\in \\{1, \\dots, N\\} $:  \n$$\n\\left( d_{i,1}^{(K)}, c_{i,1}^{(K)} \\right), \\left( d_{i,2}^{(K)}, c_{i,2}^{(K)} \\right), \\dots, \\left( d_{i,N}^{(K)}, c_{i,N}^{(K)} \\right)\n$$  \nwhere values are output as:  \n- If $ d_{i,j}^{(K)} = \\infty $, output \"inf\" for fatigue and $ 0 $ for count.  \n- Otherwise, output $ d_{i,j}^{(K)} $ and $ c_{i,j}^{(K)} \\mod (10^9 + 7) $.  \n\n**Note**: This is equivalent to computing the $ K $-th power of the (min, +) semiring matrix with counting, over the graph $ G $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10088L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}