//拓扑序列 + dijkstra
#include<bits/stdc++.h>
using namespace std;
const int T = 3e4, MAX = 2e5+10, inf = 0x3f3f3f3f;
typedef pair<int, int> PII;
int t, r, p, s;
int h[T], e[MAX], ne[MAX], w[MAX], idx;
int id[T]; //每个点属于哪个块
int cnt; //块的个数
vector<int> block[T]; //每个块包含哪些点
int dig[T]; //每个块的入度
int dis[T];
bool vis[T];
queue<int> q;
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int k){
id[k] = cnt;
block[cnt].push_back(k);
for(int i=h[k]; ~i; i=ne[i]){
int j = e[i];
if(!id[j]) dfs(j);
}
}
void dijkstra(int k){
priority_queue<PII, vector<PII>, greater<PII>> pq;
for(auto u : block[k]) pq.push({dis[u], u});
while(pq.size()){
PII t = pq.top();
pq.pop();
int u = t.second;
if(vis[u]) continue;
vis[u] = true;
for(int i=h[u]; ~i; i=ne[i]){
int j = e[i];
if(id[j]!=k && (--dig[id[j]])==0) q.push(id[j]);
if(dis[j]>dis[u]+w[i]){
dis[j] = dis[u]+w[i];
if(id[j]==k) pq.push({dis[j], j});
}
}
}
}
void solve(){
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
for(int i=1; i<=cnt; i++){
if(!dig[i]) q.push(i);
}
while(q.size()){
int t = q.front();
q.pop();
dijkstra(t);
}
}
int main(){
scanf("%d%d%d%d", &t, &r, &p, &s);
memset(h, -1, sizeof h);
int a, b, c;
for(int i=0; i<r; i++){
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
//将点根据连通性划分为块
for(int i=1; i<=t; i++){
if(!id[i]){
cnt++;
dfs(i);
}
}
for(int i=0; i<p; i++){
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
dig[id[b]]++;
}
solve();
for(int i=1; i<=t; i++){
if(dis[i]>inf/2) cout<< "NO PATH"<< endl;
else cout<< dis[i]<< endl;
}
return 0;
}