1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=25005,M=150005;

 4 int head[N],to[M],nxt[M],edge[M],mark[M],tot;

 5 int n,m,p,s,c[N],cnt,deg[N],d[N];

 6 bool v[N];

 7 queue<int> q;

 8 vector<int> a[N];

 9 priority_queue<pair<int,int> > heap;

10

11 void add(int x,int y,int z,int k){

12     nxt[++tot]=head[x];head[x]=tot;to[tot]=y;

13     mark[tot]=k;edge[tot]=z;

14 }

15

16 void dfs(int x){

17     c[x]=cnt;

18     a[cnt].push_back(x);

19     for(int i=head[x];i;i=nxt[i]){

20         if(mark[i]==1) continue;//单向边就跳过

21         int y=to[i];

22         if(!c[y]) dfs(y);

23     }

24 }

25

26 void dijkstra(int k){//算ｋ这一块的最短路

27       for(int j=0;j<a[k].size();j++){//将块中每个点取出

28           int x=a[k][j];

29           heap.push(make_pair(-d[x],x));

30       }

31       while(!heap.empty()){

32           int x=heap.top().second;heap.pop();

33           if(v[x]) continue;

34           v[x]=1;

35           for(int i=head[x];i;i=nxt[i]){

36               int y=to[i];

37               if(mark[i]==0){

38                   if(d[y]>d[x]+edge[i]){

39                       d[y]=d[x]+edge[i];

40                       heap.push(make_pair(-d[y],y));

41                 }

42             }else{

43                 d[y]=min(d[y],d[x]+edge[i]);

44                 if(--deg[c[y]]==0) q.push(c[y]);//入度为0加入队列

45             }

46         }

47     }

48 }

49

50 int main(){

51     scanf("%d%d%d%d",&n,&m,&p,&s);

52     for(int i=1;i<=m;i++){

53         int x,y,z;

54         scanf("%d%d%d",&x,&y,&z);

55         add(x,y,z,0);

56         add(y,x,z,0);//双向边

57     }

58     for(int i=1;i<=p;i++){

59         int x,y,z;

60         scanf("%d%d%d",&x,&y,&z);

61         add(x,y,z,1);

62     }

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

64         if(c[i]==0){

65             cnt++;

66             dfs(i);

67         }

68     }

69     for(int x=1;x<=n;x++){//统计每个连通块总入度

70         for(int i=head[x];i;i=nxt[i]){

71             if(mark[i]==0) continue;

72             deg[c[to[i]]]++;

73         }

74     }

75     for(int i=1;i<=cnt;i++)//拓扑排序

76         if(!deg[i]) q.push(i);

77     memset(d,0x3f,sizeof(d));

78     d[s]=0;

79     while(!q.empty()){

80         int k=q.front();q.pop();//块号

81         dijkstra(k);

82     }

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

84         if(d[i]>n*10000) puts("NO PATH");

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

86     }

87 }