#define LOCAL
#include<bits/stdc++.h>

using namespace std;
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            #define SIZE (1<<20)
            char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(p3=out,1,SIZE,stdout))
            #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        template<typename type>
        inline void read(type &x)
        {
            x=0;bool flag(0);char ch=getchar();
            while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            flag?x=-x:0;
        }
        template<typename type>
        inline void write(type x,bool flag=1)
        {
            x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
            do Stack[++top]=x%10,x/=10;while(x);
            while(top) putchar(Stack[top--]|48);
            flag?putchar('\n'):putchar(' ');
        }
        #ifndef LOCAL
            #undef SIZE
            #undef getchar
            #undef putchar
            #undef flush
        #endif
    }
}using namespace ly::IO;
int n,m,s,mp[1005][1005];
int dis[1005],times[1005];
bool flag[1005],vst[1005];
int head[100005],cnt;
struct edge{
	int to;
	int next;
	int val;
}e[100005];
void add(int u,int v,int w){
	e[cnt++].to=v;
	e[cnt].next=head[u];
	e[cnt].val=w;
	head[u]=cnt;
}
bool spfa_(int start){
	int i,p;
	queue<int> q;
	memset(vst,0,sizeof(vst));
	memset(times,0,sizeof(times));
	for(i=1;i<=n;i++){
		dis[i]=0x3f3f3f3f;
	}
	dis[start]=0;
	vst[start]=1;
	q.push(start);
	times[start]++;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vst[p]=0;
		for(int i=head[p];i;i=e[i].next){
			int x=e[i].to;
			if(dis[x]+e[i].val<dis[i]){
				dis[i]=dis[x]+e[i].val;
				if(!vst[i]){
					q.push(i);
					times[i]++;
					if(times[i]>n){
						return 1;
					}
					vst[i]=1;
				}
			}
		}
	}
	return 0;
}
void spfa(int x){
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	memset(flag,0,sizeof(flag));
	dis[x]=0;
	q.push(x);
	flag[x]=1;
	int k;
	while(!q.empty()){
		k=q.front();
		for(int i=head[k];i;i=e[i].next){
			int x=e[i].to;
			if(e[i].val>0&&dis[i]>dis[x]+e[i].val){
				dis[i]=dis[x]+e[i].val;
				if(!flag[i]){
					q.push(i);
					flag[i]=1;
				}
			}
		}
		flag[q.front()]=0;
		q.pop();
	}
}
signed main()
{
    read(n);read(m);read(s);
    for(int i=1;i<=m;i++){
    	int a,b,c;
    	read(a);read(b);read(c);
    	add(a,b,c);
	}
	for(int i=1;i<=n;i++){
		if(spfa_(i)){
			cout<<-1;
			return 0;
		}
	}
	spfa(s);
	for(int i=1;i<=n;i++){
		if(dis[i]==INT_MAX){
			cout<<"NoPath"<<"\n";
		}
		else{
			write(dis[i]);
		}
	}
    return 0;
}

求条