#include<bits/stdc++.h>
#define up(a,b,c)for(int a=b;a<=c;++a)
const int N=11e5,inf=1e9;
using namespace std;
int n,x,y,s,fa[N],ds[N],cc[N];
struct edge
{
	int v,w;
	bool operator < (edge b)const
	{
		return b.w<w;
	}
};
vector<edge>to[N],at[N];
vector<int>ccf[N];
priority_queue<edge>bbc;
void dfs(int u)
{
	if(!fa[u])
	{
		fa[u]=x,ccf[x].push_back(u);
		for(edge z:to[u])dfs(z.v);
	}
}
void dj(int s)
{
	s=fa[s];
	for(int u:ccf[s])
		if(ds[u]<inf)bbc.push({u,ds[u]});
	while(!bbc.empty())
	{
		int u=bbc.top().v;bbc.pop();
		for(edge z:to[u])
			if(ds[z.v]>ds[u]+z.w)
				bbc.push({z.v,ds[z.v]=ds[u]+z.w});
		for(edge z:at[u])
			ds[z.v]=min(ds[u]+z.w,ds[z.v]);
		while(!bbc.empty()&&ds[bbc.top().v]<bbc.top().w)bbc.pop();
	}
	for(int u:ccf[s])
		for(edge z:at[u])
		{
			--cc[fa[z.v]];
			if(!cc[fa[z.v]])dj(z.v); 
		}
			
}
int main()
{
	cin>>n>>x>>y>>s;
	fill(ds,ds+n+1,inf),ds[s]=0;
	while(x--)
	{
		int u,v,w;cin>>u>>v>>w;
		to[u].push_back({v,w}),
		to[v].push_back({u,w});
	}
	up(i,1,n)if(!fa[i])x=i,dfs(i);
	while(y--)
	{
		int u,v,w;cin>>u>>v>>w;
		at[u].push_back({v,w}),++cc[fa[v]];
	}
	up(i,1,n)if(fa[i]==i&&!cc[i])dj(i);
	up(i,1,n)
		if(ds[i]<inf)
		{
			for(edge z:to[i])
				assert(ds[z.v]<=ds[i]+z.w);
		}
	up(i,1,n)
		if(ds[i]<inf)cout<<ds[i]<<'\n';
		else cout<<"NO PATH\n";
	return 0;
}