Exact K-Step Shortest Path

You are given a weighted directed graph with n nodes and m edges, which may contain multiple edges and self-loops. Your task is to compute, for each node, the minimum path weight from node 1 if you travel along exactly k edges. The weight of a path is defined as the sum of the weights of its edges. If there is no path with exactly k edges to a node, output -1 for that node.

All answers should be output modulo $$998244353$$. There are multiple test cases.

Note on the mathematical formulation:

For a path with edges \(e_1, e_2, \dots, e_k\) with weights \(w_1, w_2, \dots, w_k\), the path weight is defined as:

$$ \text{Path Weight} = w_1 + w_2 + \cdots + w_k. $$

You need to compute the minimum such sum for each vertex and then take the result modulo $$998244353$$.

inputFormat

The first line contains a single integer T representing the number of test cases.

Each test case begins with a line containing three integers n, m, and k --- the number of nodes, the number of edges, and the exact number of edges to be used in the path, respectively.

Then m lines follow, each containing three integers u, v, and w, indicating there is a directed edge from node u to node v with weight w.

outputFormat

For each test case, output a single line containing n space-separated integers. The i-th integer denotes the minimum path weight from node 1 to node i using exactly k edges, modulo $$998244353$$. If no such path exists, output -1 for that node.

sample

3
3 3 2
1 2 3
2 3 4
1 3 10

-1 -1 7