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

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

输入格式

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

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

对于每组数据：

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

输出格式

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

样例 1

输入

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

样例 2

见下发文件 ex_matrix1.in/ans。

样例 3

见下发文件 ex_matrix2.in/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 $。

时间限制 3.00s，空间限制 2G。