Given a directed graph with $n$ vertices and $m$ weighted edges, which may contain multiple edges and self-loops, find the minimum path weight from vertex $1$ to every other vertex using exactly $k$ edges, modulo $998244353$. If no such path exists, output $-1$. There are multiple test cases.

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

Input

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, k$.
• The next $m$ lines each contain three integers $u, v, w$, representing a directed edge.

Output

For each test case, output a single line containing $n$ space-separated integers representing the answers.

Examples

Input 1

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

Output 1

-1 -1 33333401 -1 33333311

Input 2

See the provided file ex_matrix1.in/ans.

Input 3

See the provided file ex_matrix2.in/ans.

Subtasks

• 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 the same 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 Subtasks #3, #4, and #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$.