#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int inf = 1e9;
int n, m, x, y, c, dist[50005], fr[50005];
vector <pair<int, int>> G[50005];
priority_queue <pair<int, int>> Q;
bool ok = true;

void bellman_ford (int k) {
    for (int i=1; i<=n; ++i)
        dist[i] = inf;

    dist[k] = 0;
    Q.push (make_pair(0, k));

    while (!Q.empty()) {
        int k = Q.top().second;
        int d = Q.top().first;
        Q.pop();

        fr[k]++;
        if (fr[k] == n) { ok = false;  return; }

        if (dist[k] == 0-d) {
            for (auto i: G[k])
                if (dist[k] + i.second < dist[i.first]) {
                    dist[i.first] = dist[k] + i.second;
                    Q.push (make_pair(-1*dist[i.first], i.first));
                }
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x >> y >> c;
        G[x].push_back (make_pair(y, c));
    }
    bellman_ford(1);

    if (ok) {
        for (int i=2; i<=n; ++i)
            g << dist[i] << ' ';
    }
    else g << "Ciclu negativ!";
    return 0;
}