#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second


typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 17;
vector<PII> g[2][N];

int has_path[N];
void dfs1(int v)
{
	has_path[v] = 1;
	FOR(t, 0, 2)
	{
		for(auto e : g[t][v])
		{
			int to = e.F;
			if(!has_path[to])
			{
				dfs1(to);	
			}
		}
	}
}
int component[N];
int used[N];
VI verts[N];
int cntin[N];

void dfs2(int v, int comp)
{
	used[v] = 1;
	component[v] = comp;
	verts[comp].PB(v);
	
	for(auto e : g[0][v])
	{
		int to = e.F;
		if(!used[to])
		{
			dfs2(to, comp);
		}
	}	
}

const int INF = 1e9;
int d[N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, x, y, s;
	cin >> n >> x >> y >> s;
	s--;
	FOR(t, 0, 2)
	{
		FOR(i, 0, x)
		{
			int a, b, w;
			cin >> a >> b >> w;
			a--; b--;
			g[t][a].PB(MP(b, w));
			if(t == 0)
			{
				g[t][b].PB(MP(a, w));
			}
		}
		swap(x, y);
	}
	dfs1(s);
	int cnt_comp = 0;
	FOR(i, 0, n)
	{
		if(has_path[i] && !used[i])
		{
			dfs2(i, cnt_comp++);
		}
	}
	FOR(v, 0, n)
	{
		if(has_path[v])
		{
			for(auto e : g[1][v])
			{
				int to = e.F;
				assert(component[v] != component[to]);
				cntin[component[to]]++;
			}
		}
	}
	FOR(v, 0, n)
		d[v] = INF;
	set<PII> q;
	FOR(i, 0, cnt_comp)
	{
		if(cntin[i] == 0)
		{
			for(int v : verts[i])
			{
				q.insert(MP(INF, v));
			}
		}
	}
	q.erase(MP(INF, s));
	d[s] = 0;
	q.insert(MP(0, s));
	while(SZ(q))
	{
		int v = q.begin()->S;
		q.erase(q.begin());
		FOR(t, 0, 2)
		{
			for(auto e : g[t][v])
			{
				int to = e.F;
				int w = e.S;
				int comp = component[to];
				
				if(t)
				{
					cntin[comp]--;
					assert(cntin[comp] >= 0);
					if(cntin[comp] == 0)
					{
						for(int u : verts[comp])
						{
							q.insert(MP(d[u], u));
						}
					}
				}
				if(d[to] < d[v] + w)
				{
					continue;
				}
				
				if(cntin[comp] == 0)
				{	
					q.erase(MP(d[to], to));
					d[to] = d[v] + w;
					q.insert(MP(d[to], to));
				}
				d[to] = d[v] + w;
			}
		}
	}
	
	FOR(i, 0, n)
	{
		if(!has_path[i])
		{
			cout << "NO PATH\n";
		}
		else
			cout << d[i] << "\n";
		
	}
	
	
	return 0;
}