도로와 항공로

농부 존은 새로운 지역에서 우유 배달 계약을 검토하고 있다. 그는 $1$번부터 $T$번까지 번호가 매겨진 $T$개의 마을에 우유를 배달해야 하며, 마을들은 최대 $R$개의 도로와 $P$개의 항공로로 연결되어 있다.

각 도로 또는 항공로는 마을 $A_i$와 마을 $B_i$를 이동 비용 $C_i$로 연결한다.

• 도로는 양방향이며 $A_i \to B_i$, $B_i \to A_i$ 어느 방향으로든 같은 비용으로 지나갈 수 있다. 도로의 비용은 항상 $0$ 이상이다: $0 \le C_i \le 10000$.
• 항공로는 입력에 주어진 방향, 즉 $A_i \to B_i$ 방향으로만 이용할 수 있다. 항공로의 비용은 음수일 수 있다: $-10000 \le C_i \le 10000$.

$A_i$에서 $B_i$로 가는 항공로가 있다면, 도로와 항공로를 어떻게 이용하더라도 $B_i$에서 $A_i$로 되돌아올 수 없음이 보장된다. (즉, 항공로 때문에 순환이 생기지 않으므로 전체 그래프에는 음의 순환이 존재하지 않는다.)

농부 존의 물류 센터는 $S$번 마을에 있다. 각 마을에 대해, $S$번 마을에서 그 마을까지 배달하는 최소 비용을 구하라. 도달할 수 없다면 그 사실을 출력한다.

제약:

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

첫째 줄에 네 정수 $T$, $R$, $P$, $S$가 공백으로 구분되어 주어진다.

다음 $R$개의 줄에는 각각 도로를 나타내는 세 정수 $A_i$, $B_i$, $C_i$가 주어진다.

그 다음 $P$개의 줄에는 각각 항공로를 나타내는 세 정수 $A_i$, $B_i$, $C_i$가 주어진다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $S$번 마을에서 $i$번 마을까지의 최소 비용을 출력하고, 도달할 수 없으면 NO PATH를 출력한다.

항공로는 한 방향으로만 이용할 수 있고 되돌릴 수 없으므로, 어떤 마을에는 전혀 도달하지 못할 수 있으며 그런 마을에는 NO PATH를 출력한다. 도로의 비용은 음수가 아니므로 도로만으로 연결된 마을들의 묶음 안에서는 일반적인 최단 경로 규칙이 성립하고, 한 방향 항공로는 이 묶음들 사이에 비순환 순서를 부여한다. 어떤 항공로도 되돌릴 수 없다는 보장 덕분에 전체 그래프에는 음의 순환이 없으며, 따라서 도달 가능한 모든 마을의 최소 비용이 유일하게 정해진다.