#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
const int man = 25e3+10, mam = 5e4+10, inf = 0x3f3f3f3f;
struct Graph {
    int hed[man], len;
    int nxt[mam<<1], to[mam<<1], dis[mam<<1];
    void Ins (int u, int v, int w) {
        to[++len] = v;
        dis[len] = w;
        nxt[len] = hed[u];
        hed[u] = len;
        return ;
    }
} G;

int n, r, p, s, tot;
int l[man], in[man], dis[man], vis[man];
vector <int> v[man];
queue <int> o;
priority_queue <pii, vector<pii>, greater<pii> > q;
void dfs (int x) {
    l[x] = tot;
    v[tot].push_back(x);
    for (int i = G.hed[x]; i; i = G.nxt[x]) if (!l[G.to[i]]) dfs(G.to[i]);
    return ;
}
void topostra (int s) {
    dis[s] = 0;
    while(!o.empty()) {
        int x = o.front();
        o.pop();
        for (int i = 0; i < v[x].size(); ++ i) q.push(mp(dis[v[x][i]], v[x][i]));
        while (!q.empty()) {
            int p = q.top().second;
            q.pop();
            if (vis[p]) continue;
            vis[p] = 1;
            for(int i = G.hed[p]; i; i = G.nxt[i]){
                int t = G.to[i], w = G.dis[i];
                if (dis[t] > dis[p]+w) {
                    dis[t] = dis[p]+w;
                    if(l[p] == l[t]) q.push(mp(dis[t], t));
                }
                if(l[p] != l[t] && !(-- in[l[t]])) o.push(l[t]);
            }
        }
    }
    return ;
}
int main () {
    memset(dis, inf, sizeof dis);
    scanf("%d%d%d%d", &n, &r, &p, &s);
    for (int u, v, w, i = 1; i <= r; ++ i) {
        scanf("%d%d%d", &u, &v, &w);
        G.Ins(u, v, w);
        G.Ins(v, u, w);
    }
    for (int i = 1; i <= n; ++ i) if (!l[i]) {
        ++ tot;
        dfs(i);
    }
    for (int u, v, w, i = 1; i <= p; ++ i) {
        scanf("%d%d%d", &u, &v, &w);
        G.Ins(u, v, w);
        ++ in[l[v]];
    }
    for(int i = 1; i <= tot; ++ i) if(!in[i]) o.push(i);
    topostra(s);
    for (int i = 1; i <= n; ++ i) {
        if (dis[i] >= inf) printf("NO PATH\n");
        else printf("%d\n", dis[i]);
    }
    return 0;
}