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