#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
int x,y,d,next;
}a[110000];int len,last[110000];
void ins(int x,int y,int d){
len++;
a[len].x=x;a[len].y=y;a[len].d=d;
a[len].next=last[x];last[x]=len;
}
int n,m,d[1100],head,tail,list[1100],kt[1100];bool v[1100],zk[1100];
int main(){
int t,st,ed,nt;
scanf("%d%d%d",&n,&m,&st);
len=0;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
}
memset(zk,false,sizeof(zk));
for(int i=1;i<=n;i++){
if(zk[i]==false){
nt=i;
memset(kt,0,sizeof(kt));
memset(v,false,sizeof(v));v[nt]=true;
head=1;tail=2;list[1]=nt;
for(int i=1;i<=n;i++)d[i]=999999999;d[nt]=0;
while(head!=tail){
int x=list[head];
for(int k=last[x];k>0;k=a[k].next){
int y=a[k].y;
if(d[y]>d[x]+a[k].d){
d[y]=d[x]+a[k].d;
if(v[y]==false){
kt[y]++;
zk[x]=true;
if(kt[y]==n+1){

printf("-1\n");
return 0;
}
v[y]=true;
list[tail++]=y;
if(tail==n+1)tail=1;

}
}
}
head++;
v[x]=false;
if(head==n+1)head=1;
}

}
}
memset(v,false,sizeof(v));v[st]=true;
head=1;tail=2;list[1]=st;
for(int i=1;i<=n;i++)d[i]=999999999;d[st]=0;
while(head!=tail){
int x=list[head];
for(int k=last[x];k>0;k=a[k].next){
int y=a[k].y;
if(d[y]>d[x]+a[k].d){
d[y]=d[x]+a[k].d;
if(v[y]==false){
v[y]=true;
list[tail++]=y;
if(tail==n+1)tail=1;

}
}
}
head++;
v[x]=false;
if(head==n+1)head=1;
}
for(int i=1;i<=n;i++){
if(d[i]==999999999)printf("NoPath\n");
else printf("%d\n",d[i]);
}
}