#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

#define N 25003

#define M 150004

using namespace std;

inline int read(){

	int ret=0;char ch=getchar();

	bool flag=0;

	while (ch<'0' || ch>'9'){

		flag=ch=='-';

		ch=getchar();

	}

	while ('0'<=ch && ch<='9'){

		ret=ret*10-48+ch;

		ch=getchar();

	}

	return flag?-ret:ret;

}

struct edge{

	int adj,next,len;

	edge(){}

	edge(int _adj,int _next,int _len):adj(_adj),next(_next),len(_len){}

} e[M];

int n,g[N],m,di[N];

void AddEdge(int u,int v,int w){

	e[++m]=edge(v,g[u],w);g[u]=m;

}

int col[N],cnt;

int q[N],qh,qt;

int a[N],start[N];

int degree[N];

int level[N];

void bfs(){

	qh=qt=0;

	memset(col,0,sizeof(col));

	for (int i=1;i<=n;++i)if (!col[i]){

		q[++qt]=i;

		col[i]=++cnt;

		start[cnt]=qt;

		while (qh<qt){

			int u=q[++qh];

			for (int i=di[u];i;i=e[i].next){

				int v=e[i].adj;

				if (col[v]) continue;

				col[v]=cnt;

				q[++qt]=v;

			}

		}

	}

	start[cnt+1]=qt+1;

	for (int i=1;i<=qt;++i) a[i]=q[i];

	memset(degree,0,sizeof(degree));

	for (int j=1;j<=n;++j)

		for (int i=g[j];i!=di[j];i=e[i].next){

			int v=e[i].adj;

			++degree[col[v]];

		}

	qh=qt=0;

	for (int i=1;i<=cnt;++i)

		if (!degree[i]) q[++qt]=i;

	int now=0;

	while (qh<qt){

		int u=q[++qh];

		level[u]=++now;

		for (int j=start[u];j<start[u+1];++j)

			for (int i=g[a[j]];i!=di[a[j]];i=e[i].next){

				int v=e[i].adj;

				if (!--degree[col[v]]) q[++qt]=col[v];

			}

	}

}

struct HeapNode{

	int pos,value;

	HeapNode(){}

	HeapNode(int _pos,int _value):pos(_pos),value(_value){}

};

inline bool operator >(const HeapNode &x,const HeapNode &y){

	return (level[col[x.pos]]>level[col[y.pos]]||level[col[x.pos]]==level[col[y.pos]]&&x.value>y.value);

}

priority_queue<HeapNode,vector<HeapNode> ,greater<HeapNode> > h;

int mind[N];

bool flag[N];

void dijkstra(int _s){

	memset(mind,127,sizeof(mind));

	memset(flag,0,sizeof(flag));

	while (!h.empty()) h.pop();

	h.push(HeapNode(_s,mind[_s]=0));

	while (!h.empty()){

		int u=h.top().pos;

		flag[u]=1;

		h.pop();

		for (int i=g[u];i;i=e[i].next){

			int v=e[i].adj;

			if (mind[v]>mind[u]+e[i].len){

				mind[v]=mind[u]+e[i].len;

				h.push(HeapNode(v,mind[v]));

			}

		}

		while (!h.empty()&&flag[h.top().pos]) h.pop();

	}

}

int main(){

	n=read();int m0=read(),m1=read(),s=read();

	memset(g,0,sizeof(g));m=1;

	while (m0--){

		int u=read(),v=read(),w=read();

		AddEdge(u,v,w);

		AddEdge(v,u,w);

	}

	for (int i=1;i<=n;++i) di[i]=g[i];

	while (m1--){

		int u=read(),v=read(),w=read();

		AddEdge(u,v,w);

	}

	bfs();

	dijkstra(s);

	for (int i=1;i<=n;++i)

		if (mind[i]>(1<<30)) puts("NO PATH");

		else printf("%d\n",mind[i]);

	return 0;

}