#include <bits/stdc++.h>
using namespace std;
const int nmx = 5e4 + 3;
vector<array<int,2>> ad[nmx];
int d[nmx];
#if 1
#define cin fin
#define cout fout
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#endif
int main(){
    int n,m;
    cin >> n >> m;
    while(m--){
        int u,v,c;
        cin >> u >> v >> c;
        ad[u].push_back({v,c});
    }

    queue<int> q;
    fill(d,d+nmx,INT_MAX);
    d[1] = 0;
    q.push(1);
    for(int i=1;i<=n+1;i++){
        if(q.empty())
            break;
        int nd = q.front();
        q.pop();
        for(auto& ed : ad[nd]){
            int to = ed[0], w = ed[1];
            if(d[to] > d[nd] + w){
                d[to] = d[nd] + w;
                q.push(to);
            }
        }
    }
    if(q.size()){
        cout << "Ciclu negativ!";
    }
    for(int i=2;i<=n;i++){
        cout << d[i] << " ";
    }
}