#include <bits/stdc++.h>
#define inf 1e7

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, k, i, x, y, c;
int d[50002], p[50002];
vector< pair<int, int> > a[50002];
bitset<50002> fr;

static inline bool calc(int x) {
    queue<int> q;
    d[x] = 0;
    fr[x] = 1;
    q.push(x);
    while(!q.empty()) {
        x = q.front();
        q.pop();
        fr[x] = 0;

        for(auto it : a[x]) {
            int ve = it.first;
            int co = it.second;
            if(d[ve] > d[x] + co){
                d[ve] = d[x] + co;
                if(!fr[ve]){
                    fr[ve] = 1;
                    q.push(ve);
                    if(++p[ve] > n) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    fin >> n >> m;
    for(i = 1; i <= n; i++) d[i] = inf;
    for(i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        a[x].push_back({y, c});
    }
    calc(1);

    if(calc(1)) {
        for(i = 2; i <= n; i++) fout << d[i] << " ";
    }
    else fout << "Ciclu negativ!";

    return 0;
}