Farmer John's Milk Distribution

Farmer John is expanding his milk distribution to T towns (where \(1 \le T \le 25000\)) connected by roads and airplane flights. There are up to R roads (\(1 \le R \le 50000\)) and up to P airplane flights (\(1 \le P \le 50000\)).

Each road or flight is described by three integers \(A_i\), \(B_i\), and \(C_i\). For roads, \(0 \le C_i \le 10000\) and they are bidirectional, meaning you can travel from \(A_i\) to \(B_i\) or vice versa for the same cost. For flights, \(-10000 \le C_i \le 10000\) and they are directed from \(A_i\) to \(B_i\). Due to regulations, if there is a flight from \(A_i\) to \(B_i\) there is no sequence of roads and flights that allows a return from \(B_i\) to \(A_i\).

Farmer John wishes to deliver milk from his distribution center at town \(S\) (\(1 \le S \le T\)) to every town with the minimum possible cost. If a town is unreachable from \(S\), output NO PATH for that town.

Your task is to compute the shortest delivery cost to every town.

inputFormat

The first line of input contains four integers: T R P S.

• T is the number of towns (\(1 \le T \le 25000\)).
• R is the number of roads (\(1 \le R \le 50000\)).
• P is the number of airplane flights (\(1 \le P \le 50000\)).
• S is the starting town.

The next R lines describe the roads. Each line contains three integers: Ai Bi Ci, indicating that there is a bidirectional road between towns Ai and Bi with cost Ci (\(0 \le C_i \le 10000\)).

The following P lines describe the flights. Each line contains three integers: Ai Bi Ci, indicating a directed flight from town Ai to town Bi with cost Ci (\(-10000 \le C_i \le 10000\)).

outputFormat

Output exactly T lines. The i-th line should contain a single integer representing the minimum delivery cost from town \(S\) to town i. If town i is unreachable, print NO PATH instead.

sample

4 3 2 1
1 2 5
2 3 5
3 4 5
1 3 -2
4 2 -3

0
0
-2
3