#include <bits/stdc++.h>

#define pii pair<int, int>
#define fs first
#define sd second

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int n, m, dist[50005];
vector<pii> g[50005];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main( ) {
    in >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w; in >> u >> v >> w;
        g[u].push_back({v, w});
    }
    for(int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    dist[1] = 0;
    pq.push({0, 1});
    int it = 1;
    while(!pq.empty() && it <= (n - 1) * m) {
        auto crt = pq.top(); pq.pop();
        for(auto nxt : g[crt.sd]) {
            if(dist[nxt.fs] > crt.fs + nxt.sd) {
                dist[nxt.fs] = crt.fs + nxt.sd;
                pq.push({dist[nxt.fs], nxt.fs});
            }
        }
        it++;
    }
    for(int i = 1; i <= n; i++)
        for(auto j : g[i])
            if(dist[i] + j.sd < dist[j.fs])
                return out << "Ciclu negativ!", 0;
    for(int i = 2; i <= n; i++)
        out << dist[i] << ' ';
    out << '\n';
    return 0;
}