#include <bits/stdc++.h>
using namespace std;
const int nmx = 5e4+4;
vector<array<int,2>> ad[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});
    }
    vector<int> d(nmx,INT_MAX),inq(nmx),cnt(nmx);
    queue<int> q;
    q.push(1);
    d[1] = 0;
    inq[1] = 1;
    while(q.size()){
        int nd = q.front();
        inq[nd] = 0;
        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;
                if(inq[to]==0){
                    q.push(to);
                    inq[to] = 1;
                    cnt[to]++;
                    if(cnt[to] > n){
                        cout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        cout << d[i] << " ";
    }
}