/**************************************************************

     Problem: 2200

     User: Tunix

     Language: C++

     Result: Accepted

     Time:688 ms

     Memory:5432 kb

 ****************************************************************/

 //BZOJ 2200

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 void read(int &v){

     v=; int sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     v*=sign;

 }

 /******************tamplate*********************/

 const int N=,INF=1e9;

 int to[N<<],next[N<<],head[N],len[N<<],cnt;

 inline void add(int x,int y,int z){

     to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; len[cnt]=z;

     to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt; len[cnt]=z;

 }

 int t[N],ne[N],h[N],l[N],tot;

 inline void ins(int x,int y,int z){

     t[++tot]=y; ne[tot]=h[x]; h[x]=tot; l[tot]=z;

 }

 /*******************edge************************/

 int in[N],n,R,P,S;

 struct node{

     int dist,num;

     bool operator < (const node &now)const{

         return dist>now.dist;

     }

 };

 int dist[N];

 priority_queue<node>Q;

 bool done[N];

 queue<int>tp;//拓扑

 int fa[N];

 int find(int x){ return fa[x]==x ? x : (fa[x]=find(fa[x]));}

 vector<int>have[N];

 void dijkstra(int x){

     int temp=;

     rep(i,have[x].size()){

         temp=have[x][i];

         Q.push((node){dist[temp],temp});

     }

     while(!Q.empty()){

         int now=Q.top().num; Q.pop();

         if (done[now]) continue;

         done[now]=;

         for(int i=head[now];i;i=next[i]){

             if (dist[to[i]]>dist[now]+len[i]){

                 dist[to[i]]=dist[now]+len[i];

                 Q.push((node){dist[to[i]],to[i]});

             }

         }

         for(int i=h[now];i;i=ne[i]){

             int set=find(t[i]);

             if (dist[t[i]]>dist[now]+l[i]){

                 dist[t[i]]=dist[now]+l[i];

                 have[set].pb(t[i]);

             }

             in[set]--;

             if (in[set]==) tp.push(set);

         }

     }

 }

 /******************dijkstra*********************/

 bool vis[N];

 void bfs(){

     queue<int>q;

     vis[S]=; q.push(S);

     while(!q.empty()){

         int x=q.front();

         q.pop();

         for(int i=head[x];i;i=next[i])

             if (!vis[to[i]]) vis[to[i]]=,q.push(to[i]);

         for(int i=h[x];i;i=ne[i]){

             ++in[find(t[i])];

             if (!vis[t[i]]) vis[t[i]]=, q.push(t[i]);;

         }

     }

 }

 void solve(){

     F(i,,n) fa[i]=i;

     F(i,,n){

         int x=find(i),y;

         for(int j=head[i];j;j=next[j]){

             y=find(to[j]);

             if (x!=y) fa[y]=x;//就是这里！！！想不通啊想不通

         }

     }

     bfs();

     //ready

     F(i,,n) { dist[i]=INF;done[i]=;}

     dist[S]=;

     tp.push(find(S));

     have[find(S)].pb(S);

     //end

     while(!tp.empty()){

         dijkstra(tp.front());

         tp.pop();

     }

     F(i,,n)

         if (dist[i]!=INF) printf("%d\n",dist[i]);

         else printf("NO PATH\n");

 }

 int main(){

     read(n); read(R); read(P); read(S);

     int x,y,z;

     F(i,,R){

         read(x); read(y); read(z);

         add(x,y,z);

     }

     F(i,,P){

         read(x); read(y); read(z);

         ins(x,y,z);

     }

     solve();

     return ;

 }