#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> gr(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, c;
        fin >> u >> v >> c;

        gr[u].emplace_back(v, c);
    }

    queue<int> q;
    vector<int> cnt(n + 1, 0);
    vector<int> d(n + 1, 1e9);
    vector<bool> inqueue(n + 1, false);

    int start = 1;

    q.push(start);
    d[start] = 0;
    inqueue[start] = true;

    while (q.size() != 0) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;

        if (cnt[node] > n) {
            fout << "Ciclu negativ!\n";
            return 0;
        }

        for (auto &x : gr[node]) {
            if (d[node] + x.second < d[x.first]) {
                d[x.first] = d[node] + x.second;
                cnt[x.first]++;

                if (inqueue[x.first] == false) {
                    inqueue[x.first] = true;
                    q.push(x.first);
                }
            }
        }
    }

    //fout << "Vectorul de distante plecand din " << start << '\n';
    for (int i = 2; i <= n; i++)
        fout << d[i] << ' ';
   
    fout << '\n';
    return 0;
}