Mia is learning data structures, this semester. Knowing this, her boyfriend, John, gives her a difficult problem, which is about Graph.
There is adirected graph with n vertices, labeled 1, 2, ...,n, and m weighted edges (u1, v1, w1), (u2, v2, w2), ..., (um, vm, wm), the i-th of which means vertex ui can go to vertex vi and the cost will be wi (1 ≤ i ≤ m). Notice that the weights of the edges can be positive, zero, or negative. In the graph, k edges (u1, u2, w1), (u2, u3, w2), ..., (uk, uk+ 1, wk) is said to be a path from vertex u1 to vertex uk+ 1, and the total cost of the path would be w1 + w2 + ... + wk (k ≥ 0, and if k = 0, the cost would be 0). The shortest paths from vertex s to vertex t are defined to be the paths with minimum cost among all the paths from vertex s to vertex t. You are given a vertex s, and you can then find the shortest paths from vertex s to any vertices (including vertex s itself). Your task is to find out how many shortest paths there are from vertex s to all the vertices in this graph, respectively. The number may be quite large, so output the number modulo 20191208. In addition, it is quite clear that in some cases, the shortest paths from vertex s to some vertex do not exist, or there are infinite number of them, in which cases, the answer would be -1.
As this problem is a little bit hard for Mia, she, now, has turned to you for help!
The first line is an integer T (1 ≤ T ≤ 20), indicates that there are T-group data.For each test case, the first line contains three integers n, m, s(1 ≤ s ≤ n ≤ 1,000, 1 ≤ m ≤ 100,000). n is the number of vertices in the graph. m is the number of edges in the graph. s is the given vertex.There are m lines following, the i-th of which contains three integers ui, vi, wi, indicating vertex ui can go to vertex vi and the cost will be wi (1 ≤ui, vi ≤n, -1,000 ≤ wi ≤ 1,000, 1 ≤ i ≤ m).
There are no more than 5 test cases with n > 100,m > 100.
For each test case, output one line, which containsnintegers (separated by a space), thei-th of which is the number of shortest paths from vertex s to vertex i modulo 20191208 (1 ≤i≤n). If the shortest paths from vertex s to vertex i (1 ≤ i ≤ n) do not exist, or if there are infinite number of them, output -1 instead. The end of line does not have any extra spaces.
For the first test case, the shortest path from vertex 1 to vertex 1 is to stay still at vertex 1 and take no moves. We count this kind of staying still as 1 as well.
The shortest paths from vertex 1 to vertex 2 are: 1 -> 2, 1 -> 2 -> 2, 1 -> 2 -> ... -> 2, so there are infinite number of them.
The shortest paths from vertex 1 to vertex 3 do not exist, since you can go through the edge (3, 3, -1) repeatedly.
The shortest paths from vertex 1 to vertex 4 do not exist, because vertex 4 is beyond reach.For the second test case, the shortest path from vertex 1 to vertex 1 is also to stay still.
The shortest path from vertex 1 to vertex 2 is: 1 -> 2.
The shortest path from vertex 1 to vertex 3 is: 1 -> 2 -> 3.
The shortest path from vertex 1 to vertex 4 is: 1 -> 2 -> 4.
The shortest paths from vertex 1 to vertex 5 are: 1 -> 2 -> 3 -> 5, 1 -> 2 -> 4 -> 5, and 1 -> 2 -> 5.