#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], 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);
    vector <int> :: iterator it1;
    vector <int> :: iterator it2;

    while( !Q.empty() && !negative_cycle ) {
        x = Q.front();
        inQ[x] = false;
        Q.pop();
        for( it1 = Graph[x].begin(), it2 = cost[x].begin() ; it1 < Graph[x].end() ; ++it1, ++it2 )
            if( best[x] + *it2 < best[*it1] ) {
                best[*it1] = best[x] + *it2;
                ++better[*it1];
                if( !inQ[*it1] ) {
                    inQ[*it1] = true;
                    Q.push(*it1);
                }

                if( better[*it1] > 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;
}