#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=25010,maxm=1e5+10,inf=1e9;
struct edge{
	int to,nxt,w;
} e[2*maxm];
struct node{
	int dis,now;
	friend bool operator < (node x,node y){
		return x.dis>y.dis;
	}
};
int n,m,r,s,head[maxn],cnt,fa[maxn],id[maxn],k,du[maxn],dis[maxn];
vector <int> block[maxn];
priority_queue <node> q;
queue <int> Q;
void add(int u,int v,int w){
	e[++cnt]={v,head[u],w};
	head[u]=cnt;
}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void dij(int x){
	while(!q.empty()) q.pop();
	for(int i=0;i<block[x].size();++i) q.push({dis[block[x][i]],block[x][i]});
	while(!q.empty()){
		node t=q.top();
		q.pop();
		for(int i=head[t.now];~i;i=e[i].nxt){
			int v=e[i].to;
			if(id[t.now]!=id[v]){
				du[id[v]]--;
				dis[v]=min(dis[v],dis[t.now]+e[i].w);
				if(!du[id[v]]) Q.push(id[v]);
			}
			else if(t.dis+e[i].w<dis[v]){
				dis[v]=t.dis+e[i].w;
				q.push({dis[v],v});
			}
		}
	}
}
void topu(){
	for(int i=1;i<=n;++i) dis[i]=inf;
	dis[s]=0;
	for(int i=1;i<=k;++i){
		if(!du[i]) Q.push(i);
	}
	while(!Q.empty()){
		int t=Q.front();
		Q.pop();
		dij(t);
	}
}
int main(){
//	freopen("P3008_2.in","r",stdin);
//	freopen("P3008_2.out","w",stdout);
	cin>>n>>m>>r>>s;
	memset(head,-1,sizeof head);
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1,u,v,w,fx,fy;i<=m;++i){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
		fx=find(u),fy=find(v);
		if(fx!=fy) fa[fx]=fy;
	}
	for(int i=1;i<=n;++i){
		if(find(i)==i){
			id[i]=++k;
		}
	}
	for(int i=1;i<=n;++i){
		id[i]=id[find(i)];
		block[id[i]].push_back(i);
	}
	for(int i=1,u,v,w;i<=r;++i){
		cin>>u>>v>>w;
		add(u,v,w);
		du[id[v]]++;
	}
//	for(int i=1;i<=k;++i){
//		for(int j=0;j<block[i].size();++j){
//			cout<<block[i][j]<<' ';
//		}
//		puts("");
//	}
	topu();
	for(int i=1;i<=n;++i){
		if(dis[i]==inf) cout<<"NO PATH\n";
		else cout<<dis[i]<<"\n";
	}
	return 0;
}