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

using namespace std;

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

int N, M, minim, C[DIM], CAZ_PARTICULAR = 0;

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

    fscanf(f,"%d %d\n",&N,&M);

    minim = 0;
    for(i=1;i<=M;i++){

        fscanf(f,"%d %d %d\n",&x,&y,&z);
        v[x].push_back( make_pair(y,z) );

        minim = min( z, minim );
    }

    for(i=1;i<=N;i++)
        C[i] = INF;
        C[1] = 0;
}

void BellFord(){
int i, nod, nod1, nod2, cost, cost1, cost2;

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

        nod  = v[1][i].first;
        cost = v[1][i].second;

        Q.push(nod);
        C[nod] = cost;

    }

    while( !Q.empty() && CAZ_PARTICULAR == 0 ){

        nod1  = Q.front();
        cost1 = C[nod1];

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

            nod2  = v[nod1][i].first;
            cost2 = v[nod1][i].second;

            if( cost1 + cost2 < C[nod2] ){

                C[nod2] = cost1 + cost2;
                Q.push( nod2 );

                if( minim < 0 && C[nod2] < N*minim ){
                    CAZ_PARTICULAR = 1;
                    break;
                }

            }

        }
        Q.pop();
    }

    if( CAZ_PARTICULAR == 1 )
        fprintf(g,"Ciclu negativ!");
    else
        for(i=2;i<=N;i++)
            fprintf(g,"%d ",C[i]);

}

int main(){

    Citire();
    BellFord();

return 0;
}