#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define DIM 50005
#define INF 1000000000
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, d[DIM], CicluNegativ = 0, minim = INF;

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) );

        minim = min( c, minim );

    }

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

}

void Rezolvare(){
int i, nod, cost, NEWnod, NEWcost;

    Q.push(1);

    while( !Q.empty() ){

        nod  = Q.front();
        cost = d[nod];

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

            NEWnod  = v[nod][i].first;
            NEWcost = v[nod][i].second;

            if( d[NEWnod] > cost + NEWcost ){

                d[NEWnod] = cost + NEWcost;

                Q.push( NEWnod );

                if( d[NEWnod] < N * minim ){
                    CicluNegativ = 1;
                    return;
                }

            }

        }

        Q.pop();

    }

    for(i=2;i<=N;i++)
        fprintf(g,"%d ",d[i]);

}

int main(){

    Citire();
    Rezolvare();

    if( CicluNegativ )
        fprintf(g,"Ciclu negativ!\n");

return 0;
}