#include <bits/stdc++.h>

using namespace std;

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

static inline bool Calc(int st) {
    queue<int> q;
    d[st] = 0;
    fr[st] = true;
    q.push(st);

    while(!q.empty()) {
        int nod = q.front();
        q.pop();
        
        fr[nod] = false;

        for(auto it : a[nod]) {
            int vec = it.y;
            int cost = it.c;
            if(d[vec] > d[nod] + cost){
                d[vec] = d[nod] + cost;
                if(!fr[vec]){
                    fr[vec] = false;
                    q.push(vec);
                    if(++p[vec] > 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({x, y, c});
    }

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

    return 0;
}