#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
const double eps=1e-8;

int n,m,s;
struct edge {
    int to;
    int w;
};
vector<edge> g[1002];
int X[101001],Y[101001],W[101001];
int d[1002];
queue<int> Q;
bool inq[1002];
int vis[1002];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m>>s;
    FOR(i,m) {
        int x,y,w;
        cin>>x>>y>>w;
        if (x==y&&w<0) {
            cout<<-1<<endl;
            return 0;
        } else if (x!=y) g[x].pb(edge{y,w});
    }
    ++n;
    FOR(i,n-1) {
        g[n].pb(edge{i,0});
    }
    memset(d,0x3f,sizeof d);
    d[n]=0;
    bool flag=0;
    Q.push(n);
    inq[n]=1;
    vis[n]=1;
    n--;
    while (Q.size()) {
        int t=Q.front();Q.pop();
        inq[t]=0;       
        for (int i=0;i<g[t].size();i++) {
            int to=g[t][i].to,w=g[t][i].w;
            if (d[to]>d[t]+w) {
                d[to]=d[t]+w;
                if (!inq[to]) {
                    Q.push(to);
                    inq[to]=1;
                    if (++vis[to]>n) {
                        flag=1;
                        break;
                    }
                }
            }
        }
        if (flag) break;
    }
    if (flag) {
        cout<<-1<<endl;
        return 0;
    }
    memset(d,0x3f,sizeof d);
    d[s]=0;
    while (Q.size()) Q.pop();;
    memset(inq,0,sizeof inq);
    Q.push(s);
    while (Q.size()) {
        int t=Q.front();Q.pop();
        inq[t]=0;
        for (int i=0;i<g[t].size();i++) {
            int to=g[t][i].to,w=g[t][i].w;
            if (d[to]>d[t]+w) {
                d[to]=d[t]+w;
                if (!inq[to]) {
                    Q.push(to);
                    inq[to]=1;
                }
            }
        }
    }
    FOR(i,n) {
        if (d[i]==inf) cout<<"NoPath"<<endl;
        else cout<<d[i]<<endl;
    }
    return 0;
}