Problem Background

Please note: This problem is not a template problem for matrix exponentiation.

Problem Description

Given a directed graph with $n$ vertices and $m$ weighted edges, which may have multiple edges and self-loops, find the minimum path value from vertex $1$ to each vertex by exactly traversing $k$ edges, modulo $998244353$. If no such path exists, output $-1$. This is a multi-case problem.

The path value is defined as the sum of the weights of all edges in the path.

Input Format

The first line contains an integer $S$ representing the subtask number.

The second line contains an integer $T$ representing the number of test cases.

For each test case:

• The first line contains three integers $n$, $m$, and $k$.
• The next $m$ lines contain three integers each, $u$, $v$, and $w$, representing a directed edge.

Output Format

For each test case, output one line with $n$ integers separated by spaces, representing the answers.

Sample Input and Output

Sample Input #1

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

Sample Output #1

-1 -1 33333401 -1 33333311

Sample Input #2

See the provided file ex_matrix1.in

Sample Output #2

See the provided file ex_matrix1.ans

Sample Input #3

See the provided file ex_matrix2.in

Sample Output #3

See the provided file ex_matrix2.ans

Notes

• Subtask #1 ($10$ points): $\sum n ^ 3\leq 10 ^ 6$, $k\leq 10 ^ {18}$.
• Subtask #2 ($15$ points): $m = 2n - 2$, and for any $1\leq i < n$, there exist edges $(i, i + 1)$ and $(i + 1, i)$ with equal weights.
• Subtask #3 ($20$ points): $m\geq 2n - 2$, and for any $(u, v)$, there exists an edge $(v, u)$ with equal weight, note that $u$ can be equal to $v$. Depends on Subtask #2.
• Subtask #4 ($15$ points): $\sum n ^ 3\leq 10 ^ 6$, depends on Subtask #1.
• Subtask #5 ($15$ points): $k\leq 10 ^ {18}$, depends on Subtask #1.
• Subtask #6 ($25$ points): No special properties. Depends on Subtask #3, #4, #5.

For all data, $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}$. It is guaranteed that $\sum n \leq 2\times 10 ^ 5$ and $\sum n ^ 3 \leq 2.7 \times 10 ^ 7$.

The solution is in the attached file paper.pdf.

见题面 Input 部分

见题面 Output 部分