//
// Created by mihai145 on 21.01.2023.
//

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, c; cin >> x >> y >> c;
        g[x].emplace_back(y, c);
    }

    vector<int> d(n + 1, 1000 * 250000), impr(n + 1, 0);
    vector<bool> inq(n + 1, false);
    d[1] = 0; inq[1] = true;

    queue<int> q;
    q.push(1);

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

        for (pair<int, int> e : g[u]) {
            int v = e.first;
            int new_cost = d[u] + e.second;

            if (new_cost < d[v]) {
                d[v] = new_cost;
                if (inq[v]) { continue; }

                q.push(v);
                inq[v] = true;
                impr[v]++;

                if (impr[v] >= n) {
                    cout << "Ciclu negativ!\n";
                    exit(0);
                }
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        cout << d[i] << ' ';
    }

    return 0;
}