#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int n, m; fin >> n >> m;
    vector<vector<pair<int, int>>> ad(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, z; fin >> x >> y >> z;
        ad[x].emplace_back(y, z);
    }

    vector<int> dp(n + 1, 1e9);
    dp[1] = 0;

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

    vector<int> cnt(n + 1);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        if (++cnt[node] > n) {
            fout << "Ciclu negativ!\n";
            fout.close();
            return 0;
        }
        for (auto arc : ad[node])
            if (dp[node] + arc.second < dp[arc.first]) {
                dp[arc.first] = dp[node] + arc.second;
                q.push(arc.first);
            }
    }

    for (int i = 2; i <= n; i++)
        fout << dp[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}