#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 50001
#define MAXM 250001
#define INFINIT (1<<30)
using namespace std;

vector <int> Graph[MAXN];
vector <int> cost[MAXN];
queue <int> Q;
bool inQ[MAXN];
int best[MAXN], prev[MAXN], better[MAXN];

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

    int n, m, x, y, c;
    bool negative_cycle = false;

    fscanf( f, "%d%d", &n, &m );

    for( int i = 0 ; i < m ; ++i ) {
        fscanf( f, "%d%d%d", &x, &y, &c );
        Graph[x].push_back(y);
        cost[x].push_back(c);
    }

    for( int i = 2 ; i <= n ; ++i )
        best[i] = INFINIT;

    inQ[1] = true;
    Q.push(1);

    while( !Q.empty() && !negative_cycle ) {
        x = Q.front();
        inQ[x] = false;
        Q.pop();
        for( int i = 0 ; i < Graph[x].size() && !negative_cycle ; ++i )
            if( best[x] + cost[x][i] < best[Graph[x][i]] ) {
                best[Graph[x][i]] = best[x] + cost[x][i];
                ++better[Graph[x][i]];
                prev[Graph[x][i]] = x;
                if( !inQ[Graph[x][i]] ) {
                    inQ[Graph[x][i]] = true;
                    Q.push(Graph[x][i]);
                }

                if( better[Graph[x][i]] > n )
                    negative_cycle = true;
            }
    }

    if( negative_cycle )
        fprintf( g, "Ciclu negativ!\n" );
    else
        for( int i = 2 ; i <= n ; ++i )
            fprintf( g, "%d ", best[i] );

    fclose( f );
    fclose( g );
    return 0;
}