T,R,P,S = map(int,input().split())
from collections import defaultdict,deque
g = defaultdict(list)
for _ in range(R):
a,b,c = map(int,input().split())
g[a].append((b,c))
g[b].append((a,c))
ids = [-1]*(1 + T) # 每个点属于哪个连通块
blocks = [[] for _ in range(T)] # 每个连通块包含的点
import sys
sys.setrecursionlimit(10**5)
def dfs(u,idx):
ids[u] = idx
blocks[idx].append(u)
for v,c in g[u]:
if ids[v] == -1:
dfs(v,idx)
from math import inf
from heapq import heappush,heappop
dist = [inf]*(T + 1)
st = [0]*(T + 1)
dist[S] = 0
def dj(bid):
# 对bid连通块跑dj
pq = []
for x in blocks[bid]:
heappush(pq,(dist[x],x))
while pq:
d,u = heappop(pq)
if st[u]:
continue
st[u] = 1
for v,c in g[u]:
if d + c < dist[v]:
dist[v] = d + c
if ids[v] == ids[u]:
heappush(pq,(dist[v],v))
if ids[v] != ids[u]:
deg[ids[v]] -= 1
if not deg[ids[v]]:
q.append(ids[v])
# 找连通块,连通块下标从0开始
bid = 0
for i in range(1,T + 1):
if ids[i] == -1:
dfs(i,bid)
bid += 1
deg = [0]*bid
for _ in range(P):
a,b,c = map(int,input().split())
g[a].append((b,c))
deg[ids[b]] += 1
# 跑拓扑序
q = deque([i for i,x in enumerate(deg) if x == 0])
while q:
dj(q.popleft())
#print(dist)
for i in range(1,T + 1):
print('NO PATH' if dist[i] == inf else dist[i])