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

using namespace std;

vector <int> v[MAXN];   // vecini
vector <int> c[MAXN];   // cost

long int N, M, d[MAXN], a[MAXN], Q[300000]; // a = aparitii

void Citire(){
long int i, X, Y, C;

    fscanf(f,"%ld %ld\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%ld %ld %ld\n",&X,&Y,&C);
        v[X].push_back(Y);
        c[X].push_back(C);
    }

}

void Rezolvare(){
long int i, k1, k2, nod, nodv, costv;

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

    k1=1; k2=1; Q[1]=1;

    while(k1<=k2){

        nod = Q[k1];
        for(i=0;i<v[nod].size();i++){
            nodv = v[nod][i]; costv = c[nod][i];
            if( d[ nodv ] > d[ nod ] + costv ){
                d[ nodv ] = d[ nod ] + costv;
                Q[ ++k2 ] = nodv;
                a[ nodv ]++;
                if( a[nodv] >= N-1 ){ fprintf(g,"Ciclu negativ!\n"); return; }
            }

        }

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

}

int main(){

    Citire();
    Rezolvare();

return 0;
}