#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 inf 0x3f3f3f3f3f3f3f3f
#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;

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 low[N], instack[N], dfn[N], bel[N], vis[N], root[N], fa[N], ru[N];
stack<int> st;
int dis[N];
vector<PII> g[N], e[N];
vector<int> scc[N];
map<PII, int> mp;
void tarjan(int u)
{
    dfn[u] = low[u] = ++dn;
    st.push(u);
    instack[u] = 1;
    for (auto [v, w] : g[u])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u])
    {
        ++tot;
        while (true)
        {
            auto v = st.top();
            st.pop();
            bel[v] = tot;
            instack[v] = 0;
            if (v == u)
                break;
        }
    }
}
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 dij(int rt)
{
    priority_queue<PII> q;
    for (auto u : scc[rt])
    {
        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 <= y; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        ru[v]++;
    }
    for (int i = 1; i <= n; i++)
    {
        scc[find(i)].push_back(i);
    }
    queue<int> q;
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!ru[find(i)] && !vis[find(i)])
        {
            q.push(find(i));
            vis[find(i)] = true;
        }
    }
    while (!q.empty())
    {
        auto p = q.front();
        q.pop();
        dij(p);
        for (auto v : scc[p])
        {
            if (dis[v] != inf)
            {
                for (auto [x, w] : g[v])
                {
                    dis[x] = min(dis[x], dis[v] + 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;
    }
}