#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;

struct Edge{
    int from,to,weight;
}temp;

int dist[1000],n,m,start;
vector<Edge>edges;

void init(){
    int from,to,weight;
    scanf("%d %d %d",&n,&m,&start);

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&temp.from,&temp.to,&temp.weight);
        edges.push_back(temp);
    }

    fill(dist,dist+n,INT_MAX);
}

void bellmanFord(){
    dist[start]=0;
    bool somethingChanged = false;

    for(int i=0;i<n-1;i++){///for each relaxation
        somethingChanged=false;

        for(int i=0;i<m;i++){
            if(dist[edges[i].from]==INT_MAX)continue;///the distance to the beginning of the edge is inf, we cant update anything

            if(dist[edges[i].from]+edges[i].weight < dist[edges[i].to]){///if this edge gives us a better path, we update
                dist[edges[i].to] = dist[edges[i].from]+edges[i].weight;
                somethingChanged=true;///mark that we changed something
            }
        }

        if(somethingChanged==false)break;///if nothing changed this time, it wont change any other time
    }

    ///we must do one more iteration to see if negative cycles exist and are reachable from the first node
    somethingChanged=false;

    for(int i=0;i<m;i++){
        if(dist[edges[i].from]==INT_MAX)continue;///the distance to the beginning of the edge is inf, we cant update anything

        if(dist[edges[i].from]+edges[i].weight < dist[edges[i].to]){///if this edge gives us a better path, we update
            dist[edges[i].to] = dist[edges[i].from]+edges[i].weight;
            somethingChanged=true;///mark that we changed something
        }
    }

    if(somethingChanged==true){
        printf("There is a negative cycle.\n");
        return;
    }
}

void print(){
    for(int i=0;i<n;i++){
        printf("%d ",dist[i]);
    }
    printf("\n");
}

int main(){
    init();
    bellmanFord();
    print();
}