#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <queue>
#include <tuple>

using namespace std;

struct Edge {
    int u, v, weight;
};

const long long INF = numeric_limits<long long>::max();

bool bellmanFord(int N, int M, vector<Edge>& edges, vector<long long>& dist) {
    dist[1] = 0;
    bool updated;

    for (int i = 1; i <= N - 1; ++i) {
        updated = false;
        for (const auto& edge : edges) {
            if (dist[edge.u] != INF && dist[edge.u] + edge.weight < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.weight;
                updated = true;
            }
        }
        if (!updated) break; // Early exit if no update is made
    }

    for (const auto& edge : edges) {
        if (dist[edge.u] != INF && dist[edge.u] + edge.weight < dist[edge.v]) {
            return true; // Negative cycle detected
        }
    }

    return false; // No negative cycle
}

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

    if (!infile || !outfile) {
        cerr << "Error opening file" << endl;
        return 1;
    }

    int N, M;
    infile >> N >> M;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        infile >> edges[i].u >> edges[i].v >> edges[i].weight;
    }

    vector<long long> dist(N + 1, INF);

    bool negativeCycle = bellmanFord(N, M, edges, dist);

    if (negativeCycle) {
        outfile << "Ciclu negativ!" << endl;
    } else {
        for (int i = 2; i <= N; ++i) {
            if (dist[i] == INF) {
                outfile << "INF ";
            } else {
                outfile << dist[i] << " ";
            }
        }
        outfile << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}