#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=1100;
vector<pair<int,int>>G[N];
int n,m,st;
LL d[N],dd[N];bool v[N]; 
bool spfa()
{
	memset(d,0x3f,sizeof(d));d[st]=0;
	memset(dd,0,sizeof(dd));
	memset(v,0,sizeof(v));
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		dd[i]=1;
		v[i]=1;
		q.push(i);
	}
    while(!q.empty())
    {
    	int x=q.front();q.pop();v[x]=0;
    	for(auto i:G[x])
    	{
    		int y=i.first,w=i.second;
    		if(d[y]>d[x]+w)
    		{
    			d[y]=d[x]+w;
    			dd[y]=dd[x]+1;if(dd[y]>n)return 1;
    			if(v[y]==0)
				{
					q.push(y),v[y]=1;
				}
    		}
    	}
    }
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&st);
    for(int i=1,x,y,w;i<=m;i++)scanf("%d%d%d",&x,&y,&w),G[x].push_back({y,w});

	if(spfa()) printf("-1\n");
	else
	{
		for(int i=1;i<=n;i++) 
		{
			if(d[i]>1e9) printf("NoPath\n");
			else printf("%d\n",d[i]);
		}
	}
    return 0;
}