1、先输入所有双向道路，然后dfs出所有连通块，计算两个数组：id[]存储每个点属于哪个连通块；
   vector<int>block[]存储每个连通块里有哪些点
2、输入所有航线，同时统计出每个连通块的入度
3、按照拓扑序，依次处理每个连通块，先将所有入度为0的连通块的编号加入队列中。
4、每次从队头取出一个连通块的编号。
5、将block[bid]中的所有点加入堆中，然后对堆中所有点做dijkstra。
6、每次取出堆中的距离最小的点ver。
7、然后遍历ver的所有邻点j，如果id[ver] == id[j]，如果j能被更新，则将j插入堆中；
   否则说明访问到一条航线，则将id[j]这个连通块的入度减一，如果减到0了，就将其插入到拓扑序的队列中

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


using namespace std;

typedef pair<int , int> PII;

const int N = 25010 , M = 150010 , INF = 0x3f3f3f3f;

int n , mr , mp , S;
int e[M] , ne[M] , h[N] , w[M] , idx;
int dist[N];
int id[N];//存储每个点所在的连通块
int bcnt;
int bin[N];
vector<int> block[N];//每一个连通块中有哪些点
queue<int> q;//在拓扑排序中用来存储连通块编号
bool st[N];

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

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

    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        if(!id[j])  dfs(j , bid);
    }
}

void dijkstra(int t)
{
    priority_queue<PII , vector<PII> , greater<PII>> heap;
    for(auto item : block[t]) heap.push({dist[item] , item});//如果没有把所有点推入，那么后面其他连通块的bin[]没法减去所有
                                                                  //前驱边，导致拓扑无法继续
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second;
        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[ver] == id[j])    heap.push({dist[j] , j});//在同一个连通块内才可以加到连通块内
            }

            if(id[ver] != id[j] && --bin[id[j]] == 0) q.push(id[j]);
        }   //如果不在同一个连通块内，给j所在的连通块的入度减一，如果为0了，就推入队列用来做之后的拓扑
    }
}

void topsort()
{
    memset(dist , 0x3f , sizeof dist);
    dist[S] = 0;//所有以S所在连通块为航线终点的连通块中的所有点以及初始入度为0的连通块内的点，都是NO PATH，
                //1、因为如果有一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到Ai。
                //2、如果入度为0，说明不存在连入该连通块的航线，自然NO PATH
                //所以只要将入度为0的连通块全推入队列，然后依次排除掉S不在的连通块，直到轮到S所在连通块即可

    for(int i = 1 ; i <= bcnt ; i++)
        if(!bin[i])
            q.push(i);

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        dijkstra(t);
    }
}

int main()
{
    cin >> n >> mr >> mp >> S;

    memset(h , -1 , sizeof h);
    while(mr--)
    {
        int a , b , c;
        cin >> 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;
        cin >> a >> b >> c;
        add(a , b , c);
        bin[id[b]]++;
    }

    topsort();//因为是有向无环图，所以一定存在拓扑序。按照拓扑序来计算距离，因为取出的连通块前面不存在连通块，
              //所以当前连通块内的每个点不可能再被前面的点更新距离，现在更新的距离就是最小的

    for(int i = 1 ; i <= n ; i++)
        if(dist[i] > INF / 2) puts("NO PATH");
        else cout << dist[i] << endl;

    return 0;
}