P9675 [ICPC 2022 Jinan R] Shortest Path

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? For each question, if such a path does not exist, the answer is considered to be $0$. A path may use one edge multiple times. Output the answer modulo $998244353$.

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

For each test case, output one integer modulo $998244353$ denoting the answer.