#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 5e4;
vector<pair<int, int>> bords[1 + MAX_N];
int dist[1 + MAX_N];

const int inf = 1e9;

int main() {
    ifstream fin( "bellmanford.in" );
    ofstream fout( "bellmanford.out" );

    int n, m;
    fin >> n >> m;

    for ( int i = 0; i < m; i ++ ) {
        int u, v, c;
        fin >> u >> v >> c;
        bords[u].emplace_back( v, c );
    }

    for ( int i = 2; i <= n; i ++ )
        dist[i] = inf;

    queue<int> bellman;
    bellman.push( 1 );
    for ( int i = 0; i < n && bellman.size(); i ++ ) {
        int s = bellman.size();
        for ( int j = 0; j < s; j ++ ) {
            int t = bellman.front();
            bellman.pop();

            for ( pair<int, int> a : bords[t] )
                if ( dist[t] + a.second < dist[a.first] ) {
                    dist[a.first] = dist[t] + a.second;
                    bellman.push( a.first );
                }
        }
    }

    int i = 1, j = 0;
    while ( i <= n && ( j == bords[i].size() || dist[i] + bords[i][j].second >= dist[bords[i][j].first] ) ) {
        if ( j == bords[i].size() ) {
            i ++;
            j = 0;
        } else
            j ++;
    }

    if ( i <= n )
        fout << "Ciclu negativ!";
    else
        for ( int i = 2; i <= n; i ++ )
            fout << dist[i] << ' ';

    return 0;
}