$\textbf{负权的问题，可以先根据连通分量缩点}$
$\bullet \text{ 将正权边根据连通分量缩点，生成点集 } V$
$\bullet \text{ 添加含有负权的边，} \textbf{构成有向无环图}$
$\bullet \text{ 有向无环图根据拓扑排序，找到单源最短路径 }$
$\quad \forall v \in V, \text{缩点后的每个连通分量}，用 \text{dijkstra}$

$\textbf{算法描述}, \ \forall x \in V$
$\textbf{i)} \quad dfs \text{ 统计 } belong[x] \text{ ，即连通分量编号}$
$\textbf{ii)} \quad \text{添加有向边，同时计数} \ deg[belong[x]]$

$\textbf{在Dijkstra的时候加入拓扑排序}$
$\text{que 用于拓扑排序，优先队列 pque 用于 Dijkstra}$
$\textbf{i)} \quad \text{所有入度为 0 的点进入 que, } \textbf{这里用的点集是缩点后的}$
$\ \ \ \quad 当然于此同时，D(st) = 0, D(V/st) = \infty$
$\textbf{ii)} \quad 执行 \text{Dijkstra} 主过程$
$\textbf{iii)} \quad \forall x \in V(G), \forall (x,y) \in E(G)$
$\quad \quad \textbf{每走一条边，都得检查 belong[x] =? belong[y]}$
$\textbf{iv)} \quad 如果 belong[x] \neq belong[y], \text{dijkstra} 不走(x,y)$
$\quad \quad (x,y) 可能是负权边，也可能不是，但总之不要丢掉$
$\quad \quad –deg[belong[y]] == 0, \ \ que.push(belong[y])$
$\textbf{v)} \quad 重复上述步骤直到 \text{ que } 中没有元素$

$\textbf{特别注意，因为 S 不一定是 } deg[ \ ] == 0 的点$
$\text{初始化的时候}, \ que.push(belong[S])$

const int maxn = 25000 + 10;
const int inf = 0x3f3f3f3f;
const int INF = 0x7f;
int N, R, P, S;

// == Graph definition ==
vector<int> G[maxn];
class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int t, int w) : to(t), weight(w) {}
};
vector<Edge> edges;

void initG() {
    _for(i, 0, maxn) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == prework ==
// usage: prework(N) to calculate connect component
int cnt = 0;
int belong[maxn];
void dfs(int x, int cnt) {
    belong[x] = cnt;
    _for(i, 0, G[x].size()) {
        int y = edges[G[x][i]].to;
        if(belong[y]) continue;
        dfs(y, cnt);
    }
}

void prework(int N) {
    _rep(i, 1, N) {
        if(!belong[i]) {
            ++cnt;
            dfs(i, cnt);
        }
    }
}
// == prework finished ==

// == use for topo sort ==
int deg[maxn];
// == topo finsihed ==

// == dijkstra with top ==
int dist[maxn];
bool vis[maxn];
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > pque;
queue<int> que;

void initDij() {
    Set(vis, 0);
    Set(dist, INF);
    dist[S] = 0;
    que.push(belong[S]);
}

void dijkstra() {
    initDij();
    _rep(i, 1, cnt) if(deg[i] == 0) que.push(i);

    while (!que.empty()) {
        int c = que.front();
        que.pop();
        _rep(i, 1, N) if(belong[i] == c) pque.push(MPR(dist[i], i));

        while (!pque.empty()) {
            int x = pque.top().second;
            pque.pop();
            if(vis[x]) continue;
            vis[x] = true;

            _for(i, 0, G[x].size()) {
                int y = edges[G[x][i]].to;
                int z = edges[G[x][i]].weight;
                if(dist[y] > dist[x] + z) {
                    dist[y] = dist[x] + z;
                    if(belong[x] == belong[y]) pque.push(MPR(dist[y], y));
                }

                if(belong[x] != belong[y] && --deg[belong[y]] == 0) que.push(belong[y]);
            }
        }
    }
}
// == dijkstra finsiehd ==

void init() {
    cnt = 0;
    Set(belong, 0);
    Set(deg, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    cin >> N >> R >> P >> S;

    // build Graph
    initG();
    _rep(i, 1, R) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        addEdge(y, x, z);
    }
    prework(N);
    // build negative Graph
    _rep(i, 1, P) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        if(belong[x] != belong[y]) ++deg[belong[y]];
    }

    // topo and dijkstra
    dijkstra();
    _rep(i, 1, N) {
        if(dist[i] >= inf) puts("NO PATH");
        else printf("%d\n", dist[i]);
    }
}