#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define INF 0x3f3f3f3f
int main(){

    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");

    int n, m;
    cin>>n>>m;

    vector< vector<pair<int, int> > > v(n+2);
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({b,c});
    }

    vector<int> dist(n+2, INF), cnt_queue(n+2, 0);
    vector<bool> in_queue(n+2, 0);
    queue<int> q;
    bool negative_cycle = 0;

    q.push(1);
    dist[1] = 0;
    in_queue[1] = 1;
    cnt_queue[1]++;

    while(!q.empty() && !negative_cycle){
        int curr = q.front();
        q.pop();
        in_queue[curr] = 0;
        for(auto next: v[curr]){
            if(dist[next.fi] > dist[curr] + next.se){
                dist[next.fi] = dist[curr] + next.se;
                if(!in_queue[next.fi]){
                    if(cnt_queue[next.fi] > n){
                        negative_cycle = 1;
                        break;
                    }
                    else{
                        q.push(next.fi);
                        in_queue[next.fi] = 1;
                        cnt_queue[next.fi]++;
                    }
                }
            }
        }
    }

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

    return 0;
}