#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define pb push_back
#define fi first
#define se second
#define sz(x) x.size()
#define lowbit(x) (x & (-x))
#define all(x) x.begin(), x.end()

// #define int long long
#define pai 3.14
#define QF ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define c1 cout << 1
#define c2 cout << 2
// #define width cout << ""
// using ll = long long;
using PII = pair<int, int>;
// using LD = long double;
const int inf = 1e9;
// mt19937_64 rnd(chrono::duration_cast<chrono::nanoseconds>(chrono::system_clock::now().time_since_epoch()).count());
constexpr int N = 3e4 + 10;
int n, x, y, s, tot, dn;
int vis[N], fa[N], ru[N], tps[N];
int dis[N];
vector<PII> g[N], e[N], nxt[N];
vector<int> scc[N];

int find(int x)
{
    if (fa[x] != x)
        return fa[x] = find(fa[x]);
    return x;
}
void uniun(int u, int v)
{
    int fu = find(u);
    int fv = find(v);
    if (fu == fv)
        return;
    fa[fu] = fv;
}
void tuopu()
{
    vector<int> sse;
    for (int i = 1; i <= n; i++)
    {
        if (!ru[fa[i]])
            sse.push_back(fa[i]);
    }
    sse.erase(unique(sse.begin(), sse.end()), sse.end());
    queue<int> t;
    for (auto v : sse)
    {
        t.push(v);
    }
    while (!t.empty())
    {
        auto p = t.front();
        t.pop();
        tps[++tot] = p;
        for (auto u : scc[p])
        {
            for (auto [v, w] : g[u])
            {
                ru[fa[v]]--;
                if (!ru[fa[v]])
                    t.push(fa[v]);
            }
        }
    }
}
void dij(int rt)
{
    priority_queue<PII> q;
    for (auto u : scc[rt])
    {
        if (dis[u] != inf)
            q.push({dis[u], u});
    }
    while (!q.empty())
    {
        auto [w, u] = q.top();
        q.pop();
        if (dis[u] != w)
            continue;
        for (auto [v, ww] : e[u])
        {
            if (dis[v] > dis[u] + ww)
            {
                dis[v] = dis[u] + ww;
                q.push({dis[v], v});
            }
        }
    }
}
void solve()
{
    cin >> n >> x >> y >> s;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        dis[i] = inf;
    }
    for (int i = 1; i <= x; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
        uniun(u, v);
    }
    for (int i = 1; i <= n; i++)
    {
        fa[i] = find(i);
    }
    for (int i = 1; i <= y; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        ru[fa[v]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        // cout << find(i) << endl;
        scc[fa[i]].push_back(i);
    }
    tuopu();
    dis[s] = 0;
    for (int i = 1; i <= tot; i++)
    {
        auto p = tps[i];
        dij(p);
        for (auto u : scc[p])
        {
            if (dis[u] == inf)
                continue;
            for (auto [v, w] : g[u])
            {
                dis[v] = min(dis[v], dis[u] + w);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == inf)
            cout << "NO PATH" << endl;
        else
            cout << dis[i] << endl;
    }
}
signed main()
{
    QF;
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
        // cout << endl;
    }
}