#include <stdio.h>
#include <vector>
#include <queue>

#define NMAXX 50000
#define INF 50000000

using namespace std;

struct EDGE {
    int node, cost;
};

vector <EDGE> graf[NMAXX];
queue <int> bfQueue;
int dist[NMAXX], counter[NMAXX], n, ok;
bool marked[NMAXX];

void bf( int node ) {
    int i, qFront;

    for( i = 0; i <= n; i++ ) {
        marked[i] = false;
        dist[i] = INF;
    }

    dist[node] = 0;
    counter[node]++;

    bfQueue.push( node );
    marked[node] = true;

    while( !bfQueue.empty() && counter[qFront = bfQueue.front()] < n ) {
        for( const EDGE& edge : graf[qFront] ) {
            if( dist[edge.node] > dist[qFront] + edge.cost ) {
                dist[edge.node] = dist[qFront] + edge.cost;
                counter[edge.node]++;

                if( !marked[edge.node] ) {
                    bfQueue.push( edge.node );
                    marked[edge.node] = true;
                }
            }
        }
        marked[qFront] = false;
        bfQueue.pop();
    }

    if( !bfQueue.empty() )
        ok = 1;
}

int main() {
    FILE *fin, *fout;
    int m, i, a, b, c;

    fin = fopen( "bellmanford.in", "r" );
    fout = fopen( "bellmanford.out", "w" );

    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        graf[--a].push_back( { --b, c } );
    }

    bf( 0 );

    if ( ok == 0 )
        for ( i = 1; i < n; i++ )
            fprintf( fout, "%d ", dist[i] );
    else
        fprintf( fout, "Ciclu negativ!\n" );

    fclose( fin );
    fclose( fout );
    return 0;
}