// 最短路 拓扑+Dijkstra 算法 O(mlogn)
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;

const int N=25005;
int n,r,p,s;
vector<pii> e[N];
int bel[N],cnt,rd[N],vis[N],d[N];
vector<int> block[N];

void dfs(int u){
  bel[u]=cnt;
  block[cnt].push_back(u);
  for(auto [v,w]:e[u]) if(!bel[v]) dfs(v);
}
void work(){
  memset(d,0x7f,sizeof d);//0x7f>0x3f
  d[s]=0;
  queue<int> q;//队列
  priority_queue<pii,vector<pii>,greater<pii> > pq;//小根堆
  q.push(bel[s]);//s块入队
  for(int i=1;i<=cnt;i++) if(!rd[i]) q.push(i);//入度为0的块入队
  while(!q.empty()){ //块外拓扑
    int b=q.front();q.pop();
    for(int u:block[b]) pq.push({d[u],u});//块内点入堆
    while(!pq.empty()){ //块内Dijkstra
      int u=pq.top().second;pq.pop();
      if(vis[u]) continue;
      vis[u]=1;
      for(auto [v,w]:e[u]){
        if(d[v]>d[u]+w){
          d[v]=d[u]+w;
          if(bel[v]==bel[u]) pq.push({d[v],v});//点入堆
        }
        if(bel[v]!=bel[u]&&(--rd[bel[v]])==0) q.push(bel[v]);//块入队
      }
    }
  }  
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>r>>p>>s;//城镇的数量，道路的数量，航线的数量，中心城镇
  for(int i=1,a,b,c;i<=r;i++){ //双向边
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  for(int i=1;i<=n;i++)if(!bel[i]) ++cnt,dfs(i);//缩点
    
  for(int i=1,a,b,c;i<=p;i++){ //单向边
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    rd[bel[b]]++;//块的入度
  }
  
  work();//拓扑+Dijkstra
  
  for(int i=1;i<=n;i++)
    if(d[i]>inf) cout<<"NO PATH"<<'\n';
    else cout<<d[i]<<'\n';
}

// 双端队列优化SPFA算法
// 距离小于队头则从队头入队，否则从队尾入队
#include<bits/stdc++.h>
using namespace std;

const int N=25010;
int n,r,p,s,a,b,c;
vector<pair<int,int>> e[N];
int d[N],inq[N];

void spfa(int s){
  memset(d,0x3f,sizeof d); d[s]=0;
  deque<int> q; q.push_back(s); inq[s]=1;
  while(q.size()){
    int u=q.front(); q.pop_front(); inq[u]=0;
    for(auto [v,w]:e[u]){
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        if(!inq[v]){
          if(q.size()&&d[v]<d[q.front()]) q.push_front(v);
          else q.push_back(v);
          inq[v]=1;
        }
      }
    }
  }
}
int main(){
  ios::sync_with_stdio(0);
  cin>>n>>r>>p>>s;
  for(int i=1; i<=r; i++){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  for(int i=1; i<=p; i++){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
  }
  
  spfa(s);
  
  for(int i=1; i<=n; i++)
    if(d[i]==0x3f3f3f3f) cout<<"NO PATH"<<"\n";
    else cout<<d[i]<<"\n";
}

#include<bits/stdc++.h>
using namespace std;
typedef pair< int, int & > PII;
const int N=25010,INF=0x3f3f3f3f;
vector< PII >G1[N], G2[N];
vector< int > scc[N];//联通分量中的点
int cnt, belong[N], rd[N], dis[N];
//belong[]表示每个点所属的联通分量，indeg[]表示联通分量的入度
bool vis[N];
void dfs(int x)//dfs洪水填充
{
    belong[x]=cnt;
    scc[cnt].push_back(x);
    for(auto i:G1[x])
        if(!belong[i.first])
            dfs(i.first);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int n,m,p,st;
    cin>>n>>m>>p>>st;
    for(int i=1,x,y,w;i<=m;i++)
    {
        cin>>x>>y>>w;
        G1[x].push_back(make_pair(y,w));
        G1[y].push_back(make_pair(x,w));
    }
    for(int i=1,x,y,w;i<=p;i++)
    {
        cin>>x>>y>>w;
        G2[x].push_back(make_pair(y,w));
    }
   
    cnt=0;memset(belong,0,sizeof(belong));
    for(int i=1;i<=n;i++)
        if(!belong[i])
            cnt++,dfs(i);

    memset(rd, 0, sizeof(rd));
    for(int i=1;i<=n;i++)
        for(auto t:G2[i])
            rd[belong[t.first]]++;

    memset(dis,0x3f ,sizeof(dis));
    dis[st]=0;
    queue<int> Q;
    for(int i=1;i<=cnt;i++)
        if(!rd[i])
            Q.push(i);
    while(!Q.empty())
    {
        int X=Q.front();Q.pop();
        priority_queue< PII,vector<PII>,greater<PII> > PQ;
        for(auto Y:scc[X])
            if(dis[Y]<INF)
                PQ.push(make_pair(dis[Y],Y));
        while(!PQ.empty())
        {
            int x=PQ.top().second, w=PQ.top().first; PQ.pop();
            if(vis[x]) continue;
            vis[x]=true;
            for(auto i:G1[x])
            {
                int y=i.first,w=i.second;
                if(dis[y]>dis[x]+w)
                    dis[y]=dis[x]+w,
                    PQ.push(make_pair(dis[Y],y));
            }
            for(auto i:G2[x])
            {
                int y=i.first,w=i.second;
                dis[y]=min(dis[y],dis[x]+w);
            }
        }
        for(int y:scc[X])
            for(auto i:G2[y])
                if(--rd[belong[i.first]]==0)
                    Q.push(belong[i.first]);;
    
    //拓扑排序和Dijkstra
    for(int i=1;i<=n;i++)
        if(dis[i]==INF)
            cout<<"NO PATH\n";
        else
            cout<<dis[i]<<'\n';
    return 0;
}