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

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

const int INF = 1e9;

int n, m;
vector<vector<pair<int, int>>> muchii(50001);
vector<int> distanta(50001, INF);
vector<int> relax_count(50001, 0);  // How many times each node is relaxed
vector<bool> in_q(50001, false);    // To prevent duplicate entries in the queue

int main() {
    in >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        in >> x >> y >> z;
        muchii[x].push_back({y, z});
    }

    queue<int> q;
    distanta[1] = 0;
    q.push(1);
    in_q[1] = true;
    relax_count[1]++;

    bool negative_cycle = false;

    while (!q.empty() && !negative_cycle) {
        int node = q.front();
        q.pop();
        in_q[node] = false;

        for (auto edge : muchii[node]) {
            int neighbor = edge.first;
            int weight = edge.second;

            if (distanta[neighbor] > distanta[node] + weight) {
                distanta[neighbor] = distanta[node] + weight;

                if (!in_q[neighbor]) {
                    q.push(neighbor);
                    in_q[neighbor] = true;
                    relax_count[neighbor]++;

                    if (relax_count[neighbor] > n) {
                        negative_cycle = true;
                        break;
                    }
                }
            }
        }
    }

    if (negative_cycle) {
        out << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; ++i) {
            if (distanta[i] == INF)
                out << "INF ";
            else
                out << distanta[i] << " ";
        }
    }

    return 0;
}