十分感谢 orz

#include <bits/stdc++.h>
#define re register int 
using namespace std;
typedef pair<int, int> pii;
const int N = 3e4 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;
struct edge
{
	int to, w, next;
}e[M];
int top, h[N];
int dist[N], in[N], id[N], fa[N], idx;
int n, mr, ml, s;
bool vis[N], used[N];
vector<int> block[N];
queue<int> tp;
priority_queue< pii, vector<pii>, greater<pii> > q;

inline void add(int x, int y, int w)
{
	e[++ top] = (edge){y, w, h[x]};
	h[x] = top;
}

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void draw()
{
	for (re i = 1; i <= n; i ++) fa[i] = i;
	
	for (re x = 1; x <= n; x ++)
		for (re i = h[x]; i; i = e[i].next)
		{
			int y = e[i].to;
			if (find(x) != find(y))
			{
				fa[find(x)] = find(y);
				
				if (id[x]) id[y] = id[x];
				else if (id[y]) id[x] = id[y];
				else id[x] = id[y] = ++ idx;
				
				if (!used[x])
					used[x] = true, block[idx].push_back(x);
				if (!used[y])
					used[y] = true, block[idx].push_back(y);
			}
		}		
/*	
	for (re i = 1; i <= n; i ++) cout << id[i] << ' '; cout << '\n';
	for (re i = 1; i <= idx; i ++)
		for (re j = 0; j < block[i].size(); j ++)
			cout << i << ' ' << block[i][j] << '\n';
*/
}

inline void dijkstra(int xid)
{
	for (re i = 0; i < block[xid].size(); i ++)
	{
		int x = block[xid][i];
		q.push(make_pair(dist[x], x));
	}
        
	while (!q.empty())
	{
		int x = q.top().second; q.pop();
		if (vis[x]) continue;
		vis[x] = true;
		
		for (re i = h[x]; i; i = e[i].next)
		{
			int y = e[i].to, w = e[i].w;
			
			if (dist[y] > dist[x] + w)
			{
				dist[y] = dist[x] + w;
				if (id[x] == id[y]) q.push(make_pair(dist[y], y));
			}
			if (id[x] != id[y] && -- id[y] == 0)
				tp.push(id[y]); 
		}
	}
		
}

inline void topsort()
{
	for (re i = 1; i <= n; i ++) dist[i] = inf;
	dist[s] = 0;
	
	for (re i = 1; i <= idx; i ++) 
		if (in[i] == 0) tp.push(i);
	
	while (!tp.empty())
	{
		int x = tp.front(); tp.pop();
		dijkstra(x);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> mr >> ml >> s;
	while (mr --)
	{
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	draw();

	while (ml --)
	{
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c);
		in[id[b]] ++;
	}
	topsort();
	
	for (re i = 1; i <= n; i ++)
		if (dist[i] == inf) cout << "NO PATH\n";
		else cout << dist[i] << '\n';
		
	return 0;
}