#include<bits/stdc++.h>

using namespace std;

vector<int> graf[50010] ,cost[50050];

int dist[50010] , cnt[50100];

queue<int> q;

int main(){

    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    int n , m ;
    in >> n >> m ;

    for(int i = 0 ; i < m ; i ++ ){
        int x, y  , c ;
        in >> x >> y >> c ;
        graf[x].push_back(y);
        cost[x].push_back(c);
    }

    q.push(1);
    for(int i = 0 ; i <= n ; i ++)
        dist[i] = 1000000005 ;

    dist[1] = 0 ;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        int l = graf[x].size();
        for(int i = 0  ; i < l ; i ++ ){
            int y = graf[x][i];
            int c = cost[x][i];
            if(dist[x] + c < dist[y]){
                dist[y] = dist[x] + c ;
                cnt[y]++;
                q.push(y);
            }

            if(cnt[y] == n){
                out << "Ciclu negativ!";
                return 0 ;
            }

        }
    }

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

    return 0 ;

}