#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
using namespace std;

#define Nmax 50002
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair

FILE *f = fopen ( "bellmanford.in", "r" );
FILE *g = fopen ( "bellmanford.out", "w" );

vector < pair < int , int > > G[Nmax];
queue < int > Q;
bitset < Nmax > inQ;
int viz[Nmax], dist[Nmax];

int main(){
    int N, M, x, y, c;
    vector < pair < int , int > > :: iterator it;

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

    memset ( dist, inf, sizeof ( dist ) );

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d%d", &x, &y, &c );
        G[x].pb ( mp ( y, c ) );
    }

    Q.push ( 1 );
    inQ[1] = 1;
    dist[1] = 0;

    while ( !Q.empty() ){
        int nod = Q.front();
        Q.pop();
        inQ[nod] = 0;
        viz[nod]++;
        if ( viz[nod] == N ){
            fprintf ( g, "Ciclu negativ!" );
            return 0;
        }

        for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
                if ( dist[it->first] > dist[nod] + it->second ){
                    dist[it->first] = dist[nod] + it->second;
                    if ( !inQ[it->first] ){
                        Q.push ( it->first );
                        inQ[it->first] = 1;
                    }
                }
        }
    }

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

    return 0;
}