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

#define MAX_N 50000
#define MAX_DIST 250000000

using namespace std;

struct node {
    int nod, cost;
    bool operator < (const node &aux) const {
        return cost > aux.cost;
    }
};

struct muchie {
    int nod, cost;
};

int dist[MAX_N], viz[MAX_N];
vector <muchie> muchii[MAX_N];
priority_queue <node> pq;

int main() {
    FILE *fin, *fout;
    int n, m, x, y, next, ciclu_negativ, c, i;
    struct node crt;

    fin = fopen( "bellmanford.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &x, &y, &c );
        x--;
        y--;
        muchii[x].push_back( { y, c } );
    }
    fclose( fin );

    dist[0] = 0;
    for ( i = 1; i < n; i++ )
        dist[i] = MAX_DIST;

    ciclu_negativ = 0;
    pq.push( { 0, 0 } );
    while ( !pq.empty() && !ciclu_negativ ) {
        crt = pq.top();
        pq.pop();
        for ( i = 0; i < muchii[crt.nod].size(); i++ ) {
            next = muchii[crt.nod][i].nod;
            if ( dist[crt.nod] + muchii[crt.nod][i].cost < dist[next] ) {
                dist[next] = dist[crt.nod] + muchii[crt.nod][i].cost;
                viz[next]++;
                if ( viz[next] > n )
                    ciclu_negativ = 1;
                pq.push( { next, dist[crt.nod] + muchii[crt.nod][i].cost } );
            }
        }
    }

    fout = fopen( "bellmanford.out", "w" );
    if ( ciclu_negativ )
        fprintf( fout, "Ciclu Negativ" );
    for ( i = 1; i < n; i++ )
        fprintf( fout, "%d ", dist[i] == -1 ? 0 : dist[i] );
    fclose( fout );

    return 0;
}