题目背景

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

题目描述

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

路径权值的定义是路径上所有边的权值之和。

输入格式

第一行一个整数 $S$ 表示子任务编号。

第二行一个整数 $T$ 表示数据组数。

对于每组数据：

• 第一行三个整数 $n, m, k$。
• 接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条有向边。

输出格式

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

1
1
5 5 101
1 2 1
2 3 100
3 4 10000
4 2 1000000
2 5 10

-1 -1 33333401 -1 33333311

见下发文件 ex_matrix1.in

见下发文件 ex_matrix1.ans

见下发文件 ex_matrix2.in

见下发文件 ex_matrix2.ans

提示

• 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 中。