410683: GYM104076 I Shortest Path
Description
You are given an undirected weighted graph $$$G$$$ with vertices $$$1, 2, \ldots, n$$$. Please output the sum of the answers to the following $$$x$$$ questions:
- The $$$i$$$-th question $$$(1\le i\le x$$$): What is the minimum length of path that starts at vertex $$$1$$$, ends at vertex $$$n$$$, and contains exactly $$$i$$$ edges?
The first line contains one integer $$$T~(1 \le T\le 2000)$$$, the number of test cases.
For each test case, the first line contains three integers $$$n, m, x~(1\le n\le 2000, 0\le m\le 5000, 1\le x\le 10^9)$$$. Each of the next $$$m$$$ lines describes an edge of the graph. Edge $$$i$$$ is denoted by three integers $$$a_i, b_i, w_i$$$ $$$(1\le a_i, b_i\le n, 1\le w_i\le 10^9)$$$, the labels of vertices it connects and its weight. Note that self-loops and parallel edges may exist.
It is guaranteed that the sum of $$$n$$$ over all test cases is no more than $$$2000$$$ and the sum of $$$m$$$ over all test cases is no more than $$$5000$$$.
OutputFor each test case, output one integer modulo $$$998244353$$$ denoting the answer.
ExampleInput4 3 2 10 1 2 5 2 3 4 3 0 1000000000 3 3 100 1 2 3 1 3 4 2 3 5 4 6 1000000000 1 2 244 1 2 325 1 4 927 3 3 248 2 4 834 3 4 285Output
125 0 15300 840659991