#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int inf=1e9;
int n,m,i,x,y,c,dist[50005],l,fr[50005],nr[50005];
vector< pair<int,int> > G[50005];
priority_queue< pair<int,int> > q;
bool ok=true;
//sorteaza dupa primul termen si la egalitate dupa al doilea
void bellmanford(int k){

    for(i=1;i<=n;++i) {
        dist[i]=inf;
        fr[i]=inf;
    }
    q.push(make_pair(0,k) );
    dist[k]=0;

    while(!q.empty()){
        k=q.top().second;
        l=q.top().first;
        q.pop();

        if(fr[k]>0-l ){
            //fr[k]-costul minim cu care l-am procesat deja pe nodul k
            nr[k]++;
            if(nr[k]==n){ ok=false; return; }
            for(auto i: G[k])
                if(dist[k]+ i.second < dist[ i.first ]){
                    dist[ i.first ]= dist[k]+ i.second;
                    q.push( make_pair(-1*dist[i.first] , i.first) );
                }
        }
        fr[k]=0-l;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i){
        f>>x>>y>>c;
        G[x].push_back( make_pair(y,c) );
    }

    bellmanford(1);
    if(ok)
        for(i=2;i<=n;++i){
            if(dist[i]==inf) g<<0<<' ';
            else g<<dist[i]<<' ';
        }
    else g<<"Ciclu negativ!";
    //daca are ciclu si il ia, inseamna ca e negativ
    //daca face improvment de n ori pt un nod, inseamna ciclu negativ

//    for(i=1;i<n;++i)
//    for(j=1;j<=m;++J)
//        if(dist[mu[j].x] + mu[j].c < dist[mu[j].y]])
//        dist[mu[j].y]] = dist[mu[j].x] + mu[j].c;
    return 0;
}