#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;
const int MAXN = 25001;

int n, x, y, s;
vector<pair<int, int>> adj1[MAXN], adj2[MAXN];

vector<int> dist;
vector<int> djs;
vector<int> toResolve;

void dijkstra() {
	priority_queue<pair<int, int>> pq;
	for (int i: djs) {
		pq.push({-dist[i], i});
	}
	djs.clear();

	while (pq.size()) {
		auto [ds, u] = pq.top(); pq.pop();
		if (dist[u] != -ds) continue;

		toResolve.push_back(u);
		for (auto [v, w]: adj1[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.push({-dist[v], v});
			}
		}
	}
}

void resolve() {
	set<int> djss;
	for (int u: toResolve) {
		for (auto [v, w]: adj2[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				djss.insert(v);
			}
		}
	}
	for (int i: djss) djs.push_back(i);
	toResolve.clear();
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> x >> y >> s;
	for (int i = 0; i < x; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj1[a].emplace_back(b, c);
		adj1[b].emplace_back(a, c);
	}
	for (int i = 0; i < y; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj2[a].emplace_back(b, c);
	}

	dist.resize(MAXN, INF);
	dist[s] = 0; djs.push_back(s);

	while (1) {
		dijkstra();
		if (toResolve.size()) resolve();
		else break;
	}

	for (int i = 1; i <= n; i++) {
		if (dist[i] == INF) {
			cout << "NO PATH\n";
		} else {
			cout << dist[i] << '\n';
		}
	}

	return 0;
}