#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

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

const int inf = 1000000000;
int n, m;

queue <int> q;

vector< pair<int, int> > edges[50005];

int counter[50005];
int dist[50005];

int main()
{
    fin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        dist[i] = inf;
    }

    int a, b, c;
    for( int i = 1; i <= m; i++ ){
        fin >> a >> b >> c;
        edges[a].push_back( {b, c} );
    }

    q.push(1);

    dist[1] = 0;

    int x;
    while( !q.empty() ){
        x = q.front();
        q.pop();

        counter[x]++;
        if( counter[x] >= n ){
            fout << "Ciclu negativ!";
            return 0;
        }

        for( auto u : edges[x] ) {
            if( dist[u.first] > dist[x] + u.second ){
                dist[u.first] = dist[x] + u.second;
                q.push(u.first);
            }
        }
    }

    for( int i = 2; i <= n; i++ ){
        fout << dist[i] << " ";
    }

    return 0;

}