Description

Original source: USACO 2011 Jan. Gold

Farmer John is investigating a new sales region for his milk distribution plan. He wants to deliver milk to $T$ towns, numbered from $1$ to $T$. These towns are connected by $R$ roads (numbered from $1$ to $R$) and $P$ routes (numbered from $1$ to $P$). Each road $i$ or route $i$ connects town $A_i$ to $B_i$ with a cost of $C_i$.

For roads, $0 \le C_i \le 10^4$, whereas the cost of routes can be quite peculiar—$C_i$ may even be negative. Roads are bidirectional, meaning you can travel from $A_i$ to $B_i$ or from $B_i$ to $A_i$, both with the same cost $C_i$. However, routes are different; they are unidirectional, allowing travel only from $A_i$ to $B_i$.

In fact, due to recent heightened terrorism concerns, certain policies have been implemented to ensure social harmony: if there is a route from $A_i$ to $B_i$, it is guaranteed that there is no path (via any combination of roads and routes) from $B_i$ back to $A_i$. Since FJ's cows are world-renowned for their reliability, he needs to transport cows to every town. He wants to find the cheapest way to send cows from the central distribution town $S$ to each town or determine if it's impossible.

Input Format

The first line contains four space-separated integers: $T, R, P, S$;

The next $R$ lines each contain three space-separated integers (representing a road): $A_i, B_i$, and $C_i$;

The following $P$ lines each contain three space-separated integers (representing a route): $A_i, B_i$, and $C_i$.

Output Format

Output $T$ lines, where the $i$-th line indicates the minimum cost to reach town $i$. If it is impossible, output NO PATH.

Sample 1

There are six towns in total. Roads exist between towns $1$ and $2$, $3$ and $4$, and $5$ and $6$, with costs $5, 5, 10$ respectively. Additionally, there are three routes: $3\to 5$, $4\to 6$, and $1\to 3$, with costs $-100, -100, -10$ respectively. FJ's central town is town $4$. FJ's cows start at town $4$ and can reach town $3$ via roads. Then, they can take routes to towns $5$ and $6$. However, it is impossible to reach towns $1$ and $2$.

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

NO PATH
NO PATH
5
0
-95
-100

Data Range and Hints

For all data, $1\le T\le 2.5\times 10^4, 1\le R,P\le 5\times 10^4, 1\le A_i,B_i,S\le T$. It is guaranteed that for all roads, $0 \le C_i \le 10^4$, and for all routes, $-10^4 \le C_i \le 10^4$.