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

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

    int n, m;
    in >> n >> m;

    vector <vector <pair <int, int>>> adia(n);
    while (m--) {
        int a, b, c;
        in >> a >> b >> c;
        a--, b--;
        adia[a].push_back({ b, c });
    }

    vector <int> dist(n, 2e9), viz(n, 0), in_queue(n, 0), q = { 0 };
    dist[0] = 0;
    in_queue[0] = 1;

    for (int i = 0; i < (int)q.size(); i++) {
        int nod = q[i];
        in_queue[nod] = 0;
        viz[nod]++;

        for (auto vec : adia[nod]) {
            if (dist[vec.first] <= dist[nod] + vec.second)
                continue;
            if (viz[vec.first] == n) {
                out << "Ciclu negativ!\n";
                return 0;
            }
            dist[vec.first] = dist[nod] + vec.second;
            if (!in_queue[vec.first])
                q.push_back(vec.first), in_queue[vec.first] = 1;
        }
    }

    for (int i = 1; i < n; i++)
        out << dist[i] << ' ';
    out << '\n';
    return 0;    
}