/*

  一个水题，水了一下午了才水过去，陷阱太多了

  这不是普通的spfa的模板，因为有些点可能起点没有连通，但是却构成了环，应该输出-1，

  却输出了一堆 NoPath，所以应该设一个inp数组，记录某个点有没有出现过，然后把所有

  没有出现过的点再spfa一遍。

*/

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#define N 1010

#define M 100010

#define INF 10000000

#define LL long long

using namespace std;

int head[N],vis[N],num[N],inp[N],n,m,flag;

LL dis[N],dis1[N];

struct node

{

    int v,pre,t;

};node e[M];

queue<int> q;

int read()

{

    char c=getchar();int num=,flag=;

    while(c<''||c>''){if(c=='-')flag=-;c=getchar();}

    while(c>=''&&c<=''){num=num*+c-'';c=getchar();}

    return num*flag;

}

void add(int cnt,int x,int y,int z)

{

    e[cnt].v=y;

    e[cnt].t=z;

    e[cnt].pre=head[x];

    head[x]=cnt;

}

void spfa(int s,LL d[])

{

    while(!q.empty())q.pop();

    vis[s]=;

    inp[s]=;

    q.push(s);

    d[s]=;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=;

        for(int i=head[x];i;i=e[i].pre)

        {

            int y=e[i].v;

            if(d[y]>d[x]+(LL)e[i].t)

            {

                d[y]=d[x]+(LL)e[i].t;

                if(!vis[y])

                {

                    inp[y]=;

                    vis[y]=;

                    num[y]++;

                    q.push(y);

                    if(num[y]>=n||d[s]<)

                    {

                        flag=;

                        return;

                    }

                }

            }

        }

    }

}

int main()

{

    n=read();m=read();int s=read();

    for(int i=;i<=n;i++)dis[i]=INF;

    for(int i=;i<=m;i++)

    {

        int x=read(),y=read(),z=read();

        add(i,x,y,z);

    }

    spfa(s,dis);

    for(int i=;i<=n;i++)

      if(!inp[i])

      {

          if(flag){printf("-1");return ;}

          spfa(i,dis1);

      }

    if(flag){printf("-1");return ;}

    for(int i=;i<=n;i++)

      if(dis[i]<dis[])cout<<dis[i]<<endl;

      else printf("NoPath\n");

    return ;

}