E. Encoded Shortest Paths
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and $$$m$$$ edges. Each edge has an integer weight $$$w$$$ satisfying $$$0\le w \lt k$$$. Parallel edges are allowed, while self-loops are not allowed.

Consider a walk that starts at vertex $$$1$$$ and traverses edges with weights $$$w_1,w_2,\dots,w_L$$$ in this order. A walk may visit vertices and edges more than once. If $$$L\ge1$$$, the total weight of the walk is

$$$$$$ w_1\cdot k^{L-1}+w_2\cdot k^{L-2}+\cdots+w_{L-1}\cdot k+w_L $$$$$$

The empty walk has total weight $$$0$$$.

For every vertex $$$v$$$, let $$$\mathrm{dist}(v)$$$ be the minimum total weight among all walks from vertex $$$1$$$ to vertex $$$v$$$. If no such walk exists, $$$\mathrm{dist}(v)$$$ is undefined.

For every vertex $$$v$$$, determine $$$\mathrm{dist}(v)$$$ modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le10^4$$$), the number of test cases.

For each test case:

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n\le2\times10^5$$$, $$$0\le m\le5\times10^5$$$, $$$1\le k\le10^9$$$), denoting the number of vertices, the number of edges, and the parameter used in the definition of total weight, respectively.

Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$, $$$0\le w \lt k$$$), denoting an undirected edge between vertices $$$u$$$ and $$$v$$$ with weight $$$w$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$5\times10^5$$$.

Output

For each test case, print one line containing $$$n$$$ integers. For each $$$1\le i\le n$$$, consider the $$$i$$$-th integer. If $$$\mathrm{dist}(i)$$$ is defined, it must be $$$\mathrm{dist}(i)$$$ modulo $$$998\,244\,353$$$; otherwise, it must be $$$-1$$$.

Example
Input
1
5 4 3
1 2 1
1 3 2
2 4 0
3 4 0
Output
0 1 2 3 -1
Note

In the sample, the empty walk gives $$$\mathrm{dist}(1)=0$$$. The one-edge walks give $$$\mathrm{dist}(2)=1$$$ and $$$\mathrm{dist}(3)=2$$$.

There are two two-edge walks from vertex $$$1$$$ to vertex $$$4$$$. Their total weights are $$$1\cdot3+0=3$$$ and $$$2\cdot3+0=6$$$, so $$$\mathrm{dist}(4)=3$$$. Vertex $$$5$$$ is unreachable from vertex $$$1$$$.