按照y总的话语写在代码中了，浅浅看一下叭~

C++ 代码

//有负权边，不能用SPFA
//Dijstra 堆优化
//拓扑图线性扫描，不会额外多扫描

//如果边权非负，可以Dijkstra mlogn
//给每个连通块一个id(道路)
//vector<int> block[], 存每一个连通块有哪些点
//航线在不同连通块之间

//1.先输入所有双向道路，然后DFS出所有连通块，计算两个数组:
//id[]存储每个点属于哪个连通块
//vector<int> block[]存储每个连通块有哪些点
//2.输入所有航线，同时统计出每个连通块的入度
//3.按照拓扑序依次处理每个连通块。
//先将所有入读为0的连通块的编号加入队列中
//4.每次从队头取出一个连通块的编号bid
//5.将该block[bid]中的所有点加入堆中，然后对堆中的所有点跑dijstra
//6.每次取出堆中最小的点ver
//7.遍历ver的所有邻点j,如果id[ver] == id[j],（说明在连通块内部）
//如果j能被更新，则将j插入堆中，如果id[ver] != id[j],
//则将id[j]的这个连通块的入度减1，如果减为0了
//则将其插入到拓扑队列

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;//河道50000， 双向路50000 * 2

int n, m, mr, mp, S;
int h[N], e[M], w[M], ne[M], idx;
int id[N];
vector<int> block[N];//vector<int> block[]存储每个连通块有哪些点
int bcnt;//连通块个数
int dist[N], din[N];
bool st[N];
queue<int> q;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int bid)
{
    id[u] = bid;
    block[bid].push_back(u);

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];//取出临点
        if (!id[j])//如果这个点没被遍历，给他也用这个id
            dfs(j, bid);
    }
}

void dijstra(int bid)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    //距离，编号
    for (auto ver : block[bid]) heap.push({dist[ver], ver});

    while (heap.size())//堆不空时
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y, distance = t.x;//编号,距离
        if (st[ver]) continue;//遍历过就下一个
        st[ver] = true;//标记一下

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                //编号等于这个点编号的话才能加入队列
                if (id[j] == id[ver])
                    heap.push({dist[j], j});
            }

            //说明它是航线,加入队列中，原来航线都搞过再加，防止
            //再重新来
            if (id[j] != id[ver] && -- din[id[j]] == 0)
                q.push(id[j]);
        }
    }
}

void topsort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    //读取全部连通块,将所有入度为0的连通块加入队列
    for (int i = 1; i <= bcnt; i ++ )
        if (!din[i])
            q.push(i);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        dijstra(t);
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &mr, &mp, &S);

    //读入路
    memset(h, -1, sizeof h);
    while (mr -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    //如果没被遍历过， 遍历一下
    for (int i = 1; i <= n; i ++ )
        if (!id[i])
            dfs(i, ++ bcnt);

    while (mp -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        din[id[b]] ++ ;//din表示入度
    }

    topsort();

    for (int i = 1; i <= n; i ++ )
        if (dist[i] > INF / 2)//判断它很大就可以
            cout << "NO PATH" << endl;
        else cout << dist[i] << endl;

    return 0;
}