//bellman-ford cu liste(coada)
#include <vector>
#include <fstream>
#include <queue>
#define INF 100000005
#define NMAX 50005
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int n,p;
vector< pair <int,int> > G[NMAX];
int d[NMAX],t[NMAX],viz[NMAX];
void citire(){
    cin>>n>>p;
    p=1;
    int i,x,y,z;
    while(cin>>x>>y>>z){
        G[x].push_back(make_pair(y,z));
    }
}
queue<int> coada;
void bellman_ford(){
    int i,j;
    vector< pair<int,int> >::iterator it;
    d[1]=0;
    viz[1]=1;
    for(i=2;i<=n;i++)
        d[i]=INF;
    coada.push(p);
    bool ok=0;
    while(!coada.empty()){
        int varf=coada.front();
        viz[varf]=0;
        for(it=G[varf].begin();it!=G[varf].end();++it)
            if(d[it->first]>d[varf]+it->second){
                d[it->first]=d[varf]+it->second;
                if(!viz[it->first]){
                    if(t[it->first]>n)
                        ok=1;
                    else{
                        viz[it->first]=1;
                        coada.push(it->first);
                        t[it->first]++;
                    }
                }
            }
        coada.pop();
    }
    if(ok==1){
        cout<<"Ciclu negativ!";
        return ;
    }
    for(i=2;i<=n;i++)
        cout<<d[i]<<' ';
}
int main(){
    citire();
    bellman_ford();
    return 0;
}