#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int inf=2000000000;
int n,m,s,q[1000000],len[100100],d[100100],next[100100],cnt,v[1100],e[1100],dist[1100],ans[1100];
bool t[1100],checked[1100],f[1100][1100];
void spfa(int s)
{
memset(q,0,sizeof(q));
memset(t,0,sizeof(t));
memset(v,0,sizeof(v));
v[s]=1;
checked[s]=1;
q[0]=s;
int l=0,r=0;
t[s]=1;
for (int i=1;i<=n;++i) dist[i]=inf;
dist[s]=0;
while (l<=r)
{
int tmp=e[q[l]];
while (tmp>0)
{
if (dist[d[tmp]]>len[tmp]+dist[q[l]])
{
dist[d[tmp]]=len[tmp]+dist[q[l]];
checked[d[tmp]]=1;
if (++v[d[tmp]]>n) {printf("-1\n");exit(0);}
if (!t[d[tmp]]) {t[d[tmp]]=1;q[++r]=d[tmp];}
}
tmp=next[tmp];
}
t[q[l++]]=0;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
cnt=0;
while (m--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if (!f[x][y]) {d[++cnt]=y;len[cnt]=z;next[cnt]=e[x];e[x]=cnt;f[x][y]=1;}
else
{
int tmp=e[x];
while (d[tmp]!=y) tmp=next[tmp];
if (len[tmp]>z) len[tmp]=z;
}
}
spfa(s);
for (int i=1;i<=n;++i)
ans[i]=dist[i];
for (int i=1;i<=n;++i)
if (!checked[i]) spfa(i);
for (int i=1;i<=n;++i)
if (ans[i]>=inf) printf("NoPath\n"); else printf("%d\n",ans[i]);
}