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

using namespace std;

vector <int> v[MAXN]; // vecinul
vector <int> c[MAXN]; // costul

long int Q[3000000];
long int N, M;
long int a[MAXN], d[MAXN]; // aparitii, distanta minima

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

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

}

void BellmanFord(){
long int i, j, k1=1, k2=0, nod, nodv, costv;

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

    for(i=0;i<v[1].size();i++){
        Q[++k2] = v[1][i];
        d[ v[1][i] ] = c[1][i];
        a[ v[1][i] ]++;
    }

    while( k1 <= k2 ){

        nod = Q[k1];

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

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

        }

        k1++;
    }

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

}

int main(){

    Citire();
    BellmanFord();

return 0;
}