#include<bits/stdc++.h>
#define N 25000
#define M 50000
#define INF 0x3f3f3f3f
using namespace std;
struct wyy {
	int v, w;
};
int n, m1, m2, s, u, v, w, num;
vector<wyy>  g[N + 10];
vector<int> b[M + 10];  //团
int idx[N + 10], rd[M + 10], d[N + 10]; //idx[i] rd[]
queue<int> q;
bool vis[N + 10];
void dfs(int x) { //搜索x的连通的点,并加入num团中
	b[num].push_back(x);
	idx[x] = num;
	for(int i=0; i<g[x].size(); i++) {
		int v = g[x][i].v;
		if (idx[v] == 0) dfs(v);
	}
}
inline void dij(int t) { //t号团内部的最短路
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > h;
	for(int i=0; i<b[t].size(); i++) {
		int v = b[t][i];
		h.push(make_pair(d[v], v));
	}
	while(h.size()) {
		int u = h.top().second;
		vis[u] = true;
		h.pop();
		for(int i=0; i<g[u].size(); i++) {
			int v = g[u][i].v;
			int w = g[u][i].w;
			if (!vis[v] && d[v] > d[u] + w) {
				d[v] = d[u] + w;
				if (idx[v] == t) h.push(make_pair(d[v], v));
			}
			if (idx[v] != t) {
				rd[idx[v]]--;
				if (rd[idx[v]] == 0) q.push(idx[v]);
			}
		}
	}
}
inline void top_sort() {
	memset(d, 0x3f, sizeof d);
	d[s] = 0;
	for(int i=1; i<=num; i++) if(rd[i]==0) q.push(i);
	while(q.size()) {
		//puts("test");
		int t = q.front();
		q.pop();
		//cout<<"团："<<t<<endl;
		dij(t);
	}
}
int main() {
	cin >> n >> m1 >> m2 >> s;
	for(int i=1; i<=m1; i++) {
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
	}
	for(int i=1; i<=n; i++) {
		if (idx[i] == 0) {//i号点新团
			num++;
			dfs(i); //搜索所有和i连通的点都属于num号团

		}
	}
	for(int i=1; i<=m2; i++) {
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
		//v所在团的入度加1
		rd[idx[v]]++;
	}
	top_sort();
	for(int i=1; i<=n; i++) {
		if (d[i] >= INF / 2) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}