P10000 [CTT Mutual Test 2023] Matrix Fast Exponentiation

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

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.

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.

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

- 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