P10000 [集训队互测 2023] 矩阵快速幂

请注意：**本题不是矩阵快速幂模板题**。

给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。 路径权值的定义是路径上所有边的权值之和。

第一行一个整数 $S$ 表示子任务编号。 第二行一个整数 $T$ 表示数据组数。 对于每组数据： - 第一行三个整数 $n, m, k$。 - 接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条有向边。

对于每组数据，输出一行 $n$ 个由空格隔开的整数表示答案。

- Subtask #1（$10$ 分）：$\sum n ^ 3\leq 10 ^ 6$，$k\leq 10 ^ {18}$。 - Subtask #2（$15$ 分）：$m = 2n - 2$，且对任意 $1\leq i < n$，存在权值相等的 $(i, i + 1)$ 和 $(i + 1, i)$。 - Subtask #3（$20$ 分）：$m\geq 2n - 2$，且对任意 $(u, v)$，存在权值相等的 $(v, u)$，注意 $u$ 可以等于 $v$。依赖于 Subtask #2。 - Subtask #4（$15$ 分）：$\sum n ^ 3\leq 10 ^ 6$，依赖于 Subtask #1。 - Subtask #5（$15$ 分）：$k\leq 10 ^ {18}$，依赖于 Subtask #1。 - Subtask #6（$25$ 分）：无特殊性质。依赖于 Subtask #3，#4，#5。 对于所有数据，$1\leq S\leq 6$，$1\leq T\leq 10 ^ 4$，$2\leq n\leq 300$，$1\leq m\leq 2n$，$1\leq k\leq 10 ^ {64}$，$1\leq u, v\leq n$，$1\leq w\leq 10 ^ {18}$。保证 $\sum n \leq 2\times 10 ^ 5$ 且 $\sum n ^ 3 \leq 2.7 \times 10 ^ 7$。 题解在附件 `paper.pdf` 中。