Background

Please note: this problem is not a matrix fast exponentiation template problem.

Problem Description

Given a weighted directed graph with $n$ vertices and $m$ edges, there may be multiple edges and self-loops. For each vertex, find the minimum path weight among all paths that start from vertex $1$ and traverse exactly $k$ edges, and output the result modulo $998244353$. If such a path does not exist, output $-1$. There are multiple test cases.

The path weight is defined as the sum of the weights of all edges on the path.

Input Format

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

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

For each test case:

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

Output Format

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

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

Hint

• 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 $(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 $(v, u)$ with the same weight. Note that $u$ may equal $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 testdata, $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 attachment paper.pdf.

Translated by ChatGPT 5