#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define ll long long
#define vi vector<int>
#define pb emplace_back
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;

template<class T>inline void read(T &x) {
	T f=1; x=0; char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}

const int M=2e5;
const int N=5e4;
const ll inf=1e18;

struct Edge {
	int u,v;
	ll w;
}e[M+5];
int head[N+5],ecnt,Head[N+5],Ecnt;
inline void adde(int u,int v,int w) { e[++ecnt].v=v;e[ecnt].w=w;e[ecnt].u=head[u];head[u]=ecnt; }
inline void add(int u,int v,int w) { adde(u,v,w); adde(v,u,w); }
inline void adde(int u,int v,ll w) { e[++ecnt].v=v;e[ecnt].w=w;e[ecnt].u=head[u];head[u]=ecnt; }
inline void add(int u,int v,ll w) { adde(u,v,w); adde(v,u,w); }

int fa[N+5];
inline int find(int x) { return (fa[x]==x)?(x):(fa[x]=find(fa[x])); }

int du[N+5],n,x,y,s,a[N+5],b[N+5],c[N+5],st;
ll dis[N+5];

vi lt[N+5];

queue<int> q;
int vs[N+5];
vector<pii> ed[N+5];
inline void bfs() {
	q.push(s);
	vs[s]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=head[u],v;i;i=e[i].u) {
			v=e[i].v;
			if(vs[v]) continue;
			vs[v]=1;
			q.push(v);
		}
	}
}

struct Node {
    int u;
	ll d;
    bool operator <(const Node& rhs) const {
        return d>rhs.d;
    }
};

priority_queue <Node> Q;
inline void dij(int S) {
	for(int X:lt[S]) Q.push((Node){X,dis[X]});
    while(!Q.empty()) {
        Node fr=Q.top(); Q.pop();
        int u=fr.u;
		ll d=fr.d;
        if(d!=dis[u]) continue;
        for (int i=head[u];i;i=e[i].u) {
            int v=e[i].v;
			ll w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                Q.push((Node){v,dis[v]});
            }
        }
    }
}

inline void solve() {
	read(n); read(x); read(y); read(s);
	rep(i,1,n) fa[i]=i,dis[i]=inf;
	st=n+1;
	rep(i,1,x) {
		int u,v,w;
		read(u); read(v); read(w);
		add(u,v,w);
		u=find(u); v=find(v);
		fa[u]=v;
	}
	rep(i,1,n) lt[find(i)].pb(i);
	rep(i,1,y) read(a[i]),read(b[i]),read(c[i]);
	dis[s]=0;
	Ecnt=ecnt;
	rep(i,1,n) Head[i]=head[i];
	rep(i,1,y) adde(a[i],b[i],c[i]);
	bfs();
	rep(i,1,n) head[i]=Head[i]; ecnt=Ecnt;
	rep(i,1,y) {
		int X=find(a[i]),Y=find(b[i]);
		if((!vs[X])||(!vs[Y])) continue;
		ed[X].pb(mp(Y,i));
		du[Y]++;
	}
	rep(i,1,n) if(find(i)==i) {
		if(!vs[i]) continue;
		if(!du[i]) q.push(i);
	}
	dis[s]=0;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		dij(u);
		for(pii v:ed[u]) {
			du[v.fi]--;
			int ei=v.se;
			dis[b[ei]]=min(dis[b[ei]],dis[a[ei]]+c[ei]);
			if(!du[v.fi]) q.push(v.fi);
		}
	}
	rep(i,1,n)
	if(dis[i]==inf) puts("NO PATH");
	else printf("%lld\n",dis[i]);
}

int main() {
	//int T; read(T); while(T--)
	solve();
}