Roads and Planes

Farmer John is researching a new milk-delivery contract in a fresh territory. He must deliver milk to $T$ towns numbered $1 \dots T$, connected by up to $R$ roads and $P$ airplane flights.

Each road or plane connects town $A_i$ to town $B_i$ with traversal cost $C_i$.

• Roads are bidirectional and may be traversed from $A_i \to B_i$ or from $B_i \to A_i$ for the same cost. A road's cost is always non-negative: $0 \le C_i \le 10000$.
• Planes may be flown only in the given direction, from $A_i \to B_i$. A plane's cost may be negative: $-10000 \le C_i \le 10000$.

It is guaranteed that whenever a plane goes from $A_i$ to $B_i$, there is no way to return from $B_i$ to $A_i$ using any sequence of roads and planes. (In other words, the flights never form a cycle, so the whole network contains no negative cycle.)

Farmer John's distribution center is in town $S$. For every town, find the cheapest total cost to deliver from town $S$ to that town, or report that no route exists.

Constraints:

• $1 \le T \le 25000$
• $1 \le R \le 50000$, $1 \le P \le 50000$
• $1 \le A_i, B_i, S \le T$

The first line contains four space-separated integers $T$, $R$, $P$, and $S$.

Each of the next $R$ lines contains three integers $A_i$, $B_i$, $C_i$ describing a road.

Each of the following $P$ lines contains three integers $A_i$, $B_i$, $C_i$ describing a plane.

Print $T$ lines. Line $i$ contains the minimum cost to travel from town $S$ to town $i$, or NO PATH if town $i$ cannot be reached from town $S$.

Because a plane can be flown in only one direction and can never be undone, some towns may be impossible to reach; those must print NO PATH. Roads have non-negative cost, so within any group of towns connected only by roads the usual shortest-path rules apply, while the one-way planes impose an acyclic ordering on those groups. The guarantee that no plane can be reversed means the whole network has no negative cycle, so every reachable town has a uniquely determined minimum cost.