RT，别的OJ上是 TLE，

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define int long long
#define PII pair<int,int>
using namespace std;

const int N=5e4+5,M=1e5+5;
int n,r,p,s;

struct EDGE{
	int val;
	int to,nxt;
}road[M],plane[M],raw_plane[M];
int ridx,rhead[N];
inline void add_road(int x,int y,int z)
{
	road[++ridx]={z,y,rhead[x]};
	rhead[x]=ridx;
	return;
}
int raw_pidx,raw_phead[N];
inline void add_raw_plane(int x,int y,int z)
{
	raw_plane[++raw_pidx]={z,y,raw_phead[x]};
	raw_phead[x]=raw_pidx;
//	printf("raw_plane[%d]:{%d, %d,%d}\n",raw_pidx,raw_plane[raw_pidx].val,raw_plane[raw_pidx].to,raw_plane[raw_pidx].nxt);
	return;
}
int pidx,phead[N];
inline void add_plane(int x,int y,int z)
{
	plane[++pidx]={z,y,phead[x]};
	phead[x]=pidx;
	return;
}

int fa[N],utot;
void uInit()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	return;
}
int uask(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=uask(fa[x]);
}
inline void umerge(int x,int y)
{
	fa[uask(y)]=uask(x);
	return;
}

int dist[N];
priority_queue<PII,vector<PII>,greater<PII>> pq;
void Dijkstra()
{
	while(!pq.empty())
	{
		int x=pq.top().second; pq.pop();
		for(int i=rhead[x];i;i=road[i].nxt)
		{
			int y=road[i].to,z=road[i].val;
//			printf("%lld -> %lld? %lld,%lld+%lld\n",x,y,dist[y],dist[x],z);
			if(dist[y]>dist[x]+z)
			{
//				printf("Yes\n");
				dist[y]=dist[x]+z;
				pq.push({dist[y],y});
			}
		}
	}
	return;
}

bool rvst[N];
queue<int> rq;
vector<int> save[N];
void Relax(int src)
{
	rq.push(src);int asd=0;
	while(!rq.empty())
	{
		int x=rq.front(); rq.pop();
//		printf("Relaxing %lld\n",x);
		rvst[x]=true;
//		printf("In this?\n");
		for(int i=raw_phead[x];i;i=raw_plane[i].nxt)
		{
			int y=raw_plane[i].to,z=raw_plane[i].val;
//			printf("Find %d: (%d) %lld->%lld (%lld)\n",i,++asd,x,y,z);
//			printf("Updating... %lld, %lld\n",dist[y],dist[x]+z);
			if(dist[x]+z<dist[y])
			{
				dist[y]=dist[x]+z;
				save[uask(y)].push_back(y);
//				printf("Saved %lld!\n",y);
			}
//			printf("Fly to %lld(%lld)\n",y,dist[y]);
		}
		for(int i=rhead[x];i;i=road[i].nxt)
		{
			int y=road[i].to;
			if(rvst[y]) continue;
			rq.push(y);
		}
	}
//	printf("RETURNED\n");
	return;
}

int deg[N],order[N],odcnt=0;
queue<int> tq;
void TopoSort()
{
	for(int i=1;i<=n;i++)
		if(fa[i]==i && !deg[i]) tq.push(i);
	while(!tq.empty())
	{
		int x=tq.front(); tq.pop();
		order[++odcnt]=x;
		for(int i=phead[x];i;i=plane[i].nxt)
		{
			int y=plane[i].to;
			deg[y]--;
			if(!deg[y]) tq.push(y);
		}
	}
	return;
}

signed main()
{
//	freopen("P3008_6.in","r",stdin);
	
	memset(dist,0x3f,sizeof(dist));
	scanf("%lld%lld%lld%lld",&n,&r,&p,&s);
	uInit();
	for(int i=1;i<=r;i++)
	{
		int x,y,z; scanf("%lld%lld%lld",&x,&y,&z);
		if(x==y) continue;
		add_road(x,y,z); add_road(y,x,z);
		umerge(x,y);
	}
	for(int i=1;i<=p;i++)
	{
		int x,y,z; scanf("%lld%lld%lld",&x,&y,&z);
		add_raw_plane(x,y,z);
		add_plane(uask(x),uask(y),z);
		deg[uask(y)]++;
	}
	TopoSort();
	dist[s]=0; pq.push({dist[s],s});
	bool start=false;
	for(int i=1;i<=odcnt;i++)
	{
		int x=order[i];
		if(uask(s)==x) start=true;
		if(!start) continue;
		for(int j=0;j<save[x].size();j++)
			pq.push({dist[save[x][j]],save[x][j]})/*,printf("next: %lld\n",save[x][j])*/;
		save[x].clear();
		Dijkstra();
		Relax(x);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(dist[i]>0x3f3f3f3f3f3f3f3f>>1) printf("NO PATH\n");
		else printf("%lld\n",dist[i]);
	}
	return 0;
}