P9675 [ICPC 2022 Jinan R] Shortest Path

给定一张 $n$ 个点 $m$ 条边的无向图 $G$，边有边权。你要回答 $x$ 个问题，其中第 $i$ $(1\leqslant i\leqslant x)$ 个问题形如： - 从结点 $1$ 出发，经过 **恰好** $i$ 条边，到达结点 $n$ 的最短路径长度为多少？ 对于每个询问，若不存在这样的路径，答案应当为 $0$。一条路径可能 **多次** 经过一条边。 求出这 $x$ 个问题所对应的答案之和。输出答案对 $998244353$ 取模后的结果。

第一行包含一个整数 $T$ $(1\leqslant T\leqslant 2000)$，表示测试数据组数。 对于每组测试数据： 第一行三个整数 $n,m,x$ $(1\leqslant n\leqslant 2000,0\leqslant m\leqslant 5000,1\leqslant x\leqslant 10^9)$。 接下来 $m$ 行，每行三个整数 $a_i,b_i,w_i$ $(1\leqslant a_i,b_i\leqslant n,1\leqslant w_i\leqslant 10^9)$，分别表示第 $i$ 条边连接的两个结点的编号和其边权。注意 **可能存在自环和重边**。 保证所有测试数据中 $n$ 的总和不超过 $2000$，且 $m$ 的总和不超过 $5000$。

对于每组测试数据，输出这组测试数据对应的答案 $\bmod$ $998244353$ 后的结果。