#include <bits/stdc++.h>
using namespace std;
struct muchie{
    int y, cost;
};
vector <muchie> v[50005];
int treceri[50005], cost[50005];
int main(){
    int n, m, i, x, y, c, neg;
    ifstream fin( "bellmanford.in" );
    ofstream fout( "bellmanford.out" );
    fin >> n >> m;
    for( i = 0; i < m; i++ ){
        fin >> x >> y >> c;
        v[x].push_back( { y, c } );
    }
    for( i = 2; i <= n; i++ ){
        cost[i] = INT_MAX;
    }
    queue <int> q;
    q.push( 1 );
    neg = 0;
    while( q.empty() == false && neg == 0 ){
        x = q.front();
        q.pop();
        for( i = 0; i < v[x].size(); i++ ){
            ///cout << x << ' ' << v[x][i].y << ' ' << v[x][i].cost << ' ' << cost[x] + v[x][i].cost << ' ' << cost[v[x][i].y] << '\n';
            if( cost[x] + v[x][i].cost < cost[v[x][i].y] ){
                cost[v[x][i].y] = cost[x] + v[x][i].cost;
                q.push( v[x][i].y );
                treceri[v[x][i].y]++;
                if( treceri[v[x][i].y] > n ){
                    neg = 1;
                }
            }
        }
    }
    if( neg == 1 ){
        fout << "Ciclu negativ!";
    }
    else{
        for( i = 2; i <= n; i++ ){
            fout << cost[i] << ' ';
        }
    }
    return 0;
}