#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 50005
#define MAXM 250005
#define INF 1000000000
FILE *f=fopen("bellmanford.in","r"), *g=fopen("bellmanford.out","w");

using namespace std;

int N, M, D[MAXN], viz[MAXM], CN = 0;

    // CN = Ciclu Negativ

queue <int> Q;
vector < pair<int,int> > v[MAXN];

void Citire(){
int i, x, y, c;

    fscanf(f,"%d %d\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%d %d %d\n",&x,&y,&c);
        v[x].push_back( make_pair(y,c) );
    }

    for(i=2;i<=N;i++)
        D[i] = INF;
}

void BellFord(){
int i, NOD, NODnou, Dnou;

    Q.push(1);

    while( !Q.empty() ){

        NOD = Q.front();

        for(i=0;i<v[NOD].size();i++){

            NODnou = v[NOD][i].first;
            Dnou = D[NOD] + v[NOD][i].second;

            if( Dnou < D[NODnou] ){

                D[NODnou] = Dnou;
                viz[NODnou] ++;
                Q.push(NODnou);

                if( viz[NODnou] > N-1 ){ CN = 1; return; }

            }

        }

        Q.pop();

    }

}

int main(){

    Citire();
    BellFord();

    if( CN == 1 )
        fprintf(g,"Ciclu negativ!\n");
    else
        for(int i=2;i<=N;i++)
            fprintf(g,"%d ",D[i]);

return 0;
}