#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 0x7f7f7f7f
using namespace std;
struct Edge{ int v,c,nt; }G[100010];
int k=0,h[1001],n,m,S,d[1001],iq[1001]={0};
bool vis[1001]={0};
inline int min(int& a,int b){if(a>b)return(a=b)|1;return 0;}
void psEdge(int a,int b,int c){
G[k]=(Edge){b,c,h[a]}; h[a]=k++;
}
int spfa(int s){
memset(d,127,sizeof d);
queue<int> q;
q.push(s); d[s]=0;
vis[s]=0; iq[s]++;
while(!q.empty()){
int x=q.front(); q.pop();
for(int v,i=h[x];~i;i=G[i].nt){
if(min(d[v=G[i].v],d[x]+G[i].c)&&!vis[v]){
q.push(v); vis[v]=1;
if(iq[v]++>n) return 1;
}
}
vis[x]=0;
}
return 0;
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&S);
for(int a,b,c,i=0;i<m;++i){
scanf("%d%d%d",&a,&b,&c);
psEdge(a,b,c);
}
if(spfa(S)) return 0&puts("-1");
for(int i=1;i<=n;++i){
if(d[i]==INF) puts("No path");
else printf("%d\n",d[i]);
}
}