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

using namespace std;

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

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

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);
    dist[1] = 0;

    for (int i = 1; i <= N - 1; ++i) {
        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;
            }
        }
    }

    bool negative_cycle = false;
    for (const auto& edge : edges) {
        if (dist[edge.u] != INF && dist[edge.u] + edge.weight < dist[edge.v]) {
            negative_cycle = true;
            break;
        }
    }

    if (negative_cycle) {
        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;
}