个人思路：

• 首先可以发现是单源最短路问题，但是负边权引起了我们的注意。
• “双向道路单向航线”、”不存在环”引起了我们的注意，可以发现缩点后是一个DAG图。
• 在DAG图上可以考虑进行拓扑排序。同时在每个联通块内部进行Dijkstra算法，问题得解。

数据注意点：

3 0 2 1
1 2 1
3 2 2
简单 拖油瓶式数据

9 9 2 1
1 2 1
1 3 3
2 3 7
4 5 2
5 6 1
4 6 6
7 8 1
8 9 1
9 7 1
3 4 5
7 6 5
普通 拖油瓶式数据

3 0 1 1
3 2 -100
简单 拓扑排序(INF)式数据

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=1000010,MAXM=1000010,INF=2100000000;
struct Edge_Default{
    int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=0;
void addEdge(int u,int v,int w){
    e[++edgeCnt].from=u;
    e[edgeCnt].to=v;
    e[edgeCnt].w=w;
    e[edgeCnt].nxt=head[u];
    head[u]=edgeCnt;
}
vector<int> scc[MAXN];//联通块
int c[MAXN];//属于的联通块的代表元 
void getScc(int fa,int x){//DFS划分联通块 
    c[x]=fa;
    scc[c[fa]].push_back(x);
    for(int i=head[x];i;i=e[i].nxt){
        int nowV=e[i].to;
        if(!c[nowV]){
            getScc(fa,nowV);
        }
    }
}
int rd[MAXN];
//从某个点开始进行dijkstra,出现不在联通块的则加入bfs队列,并减少入度 
struct Node{
    int nowPoint,nowValue;
    bool operator <(const Node &a)const{
        return a.nowValue<nowValue;
    }
};
queue<int> topoQueue;
int dis[MAXN];
void dijkstra(int x){
    priority_queue<Node> q;
    if(!scc[c[x]].empty()){
        int siz=scc[c[x]].size();
        for(int j=0;j<siz;j++){
            int nowSccPoint=scc[c[x]].at(j);
            q.push(Node{nowSccPoint,dis[nowSccPoint]});
        }
    }
    while(!q.empty()){
        Node nowNode=q.top();q.pop();
        int nowPoint=nowNode.nowPoint,nowValue=nowNode.nowValue;
        if(dis[nowPoint]!=nowValue)continue;
        for(int i=head[nowPoint];i;i=e[i].nxt){
            int toV=e[i].to,fromV=e[i].from;
            bool isSameScc=(c[x]==c[toV]);
            if(!isSameScc){
                rd[c[toV]]--;
                if(!rd[c[toV]]){
                    topoQueue.push(c[toV]);
                }
            }
            if(dis[fromV]==INF)continue;//*防止拓扑排序(INF)类数据
            if(dis[toV]>dis[fromV]+e[i].w){
                dis[toV]=dis[fromV]+e[i].w;
                if(isSameScc)q.push(Node{toV,dis[toV]});
            }
        }
    }
}
int s,vis[MAXN];
int n;
void solve(){
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    for(int i=1;i<=n;i++){
        if(!vis[c[i]]&&(c[i])&&(!rd[c[i]])){
            vis[c[i]]=1;
            topoQueue.push(c[i]);//*防止拖油瓶式数据 
        }
    }
    while(!topoQueue.empty()){
        int nowV=topoQueue.front();topoQueue.pop();//当前所在的联通块
        dijkstra(nowV);//在当前联通块进行dijkstra 
    }
}
int main(){
    memset(c,0,sizeof(c));
    memset(rd,0,sizeof(rd));
    int m,p;//m 双向 p单向存负
    scanf("%d%d%d%d",&n,&m,&p,&s);
    for(int i=1;i<=n;i++)dis[i]=INF;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    for(int i=1;i<=n;i++)
        if(!c[i])
            getScc(i,i);
    for(int i=1;i<=p;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        rd[c[v]]++;
    }
    solve();
    for(int i=1;i<=n;i++){
        if(dis[i]==INF)cout<<"NO PATH"<<endl;
        else cout<<dis[i]<<endl;
    }
    return 0;
}