#include<iostream>
#include<vector>
#include<queue>
#include <climits>
using namespace std;
#define ll int
#define pb(x,y,w) e[x].push_back({y,w})
ll n,p,r,s,to,val;
ll u,v,w;
struct node{
	ll to,v;
};
vector<node>e[30004];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
ll f[30004];
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n=read();
	r=read();
	p=read();
	s=read();
	for(int i=1;i<=r;i++){
		u=read();
		v=read();
		w=read();
		pb(u,v,w);
		pb(v,u,w);
	}
	for(int i=1;i<=p;i++){
		u=read();
		v=read();
		w=read();
		pb(u,v,w);
	}
	for(int i=1;i<=n;i++) f[i]=INT_MAX;
	f[s]=0;
	q.push({0,s});
	while(!q.empty()){
		u=q.top().second,w=q.top().first;
		q.pop();
		if(w!=f[u]) continue;
		for(int i=0;i<e[u].size();i++){
			to=e[u][i].to,val=e[u][i].v;
			if(f[to]>f[u]+val)
			{
				f[to]=f[u]+val;
				q.push({f[to],to});
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]==INT_MAX){
			printf("NO PATH");
		}
		else
		write(f[i]);
		printf("\n");
	}
}

寄