8481: Path

Given a graph with n vertices and m edges.Each vertex is numbered from 1 to n.
Each edge i has its cost w i ,some edges are common edges and some edges are special edges.
When you pass through a special edge, the next step after passing this edge,you can reach any vertex
in the graph. if you goto the vertice which an original edge i can arrived from current vertice, the cost
become w i − K(0 ≤ w i − K)(if you used edge i), otherwise the cost will become 0(every vertice except
the vertice which original edge can arrived from current vertice)
original edge includes all common edges and special edges.
Now you start at S,You need to calculate the minimum cost from the starting vertex to each vertex(If
there is a situation where you cannot reach, please output "−1 ")

Each test contains multiple test cases. The first line contains the number of test cases T. Description of
the test cases follows.
The first line of each test case contains four integers n,m,S,K
The next m lines each line contains four integers x,y,w,t represent an directed edge connect x and y with
cost w,t = 0 represents it’s a common edge,t = 1 represents it’s a special edge.
1 ≤sigema(m),sigema(m) ≤ 10 6 ,1 ≤ x,y,S ≤ n,1 ≤ w,K ≤ 10 9
K ≤ w i (1 ≤ i ≤ m)

For each test case, print n integer in a line— the answer to the problem. There is a space at the end of
the line for each line.when you cannot reach, please output −1.

2
5 4 1 1
1 2 4 0
1 3 5 0
3 4 3 1
4 5 3 0
5 3 1 1
1 2 4 0
1 3 5 0
3 4 3 1

0 4 5 8 10
0 4 5 8 8