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

using namespace std;

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

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

bool spfa(int N, int M, vector<Edge>& edges, vector<long long>& dist) {
    vector<int> inQueue(N + 1, 0);
    vector<int> count(N + 1, 0);
    queue<int> q;

    dist[1] = 0;
    q.push(1);
    inQueue[1] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = 0;

        for (const auto& edge : edges) {
            if (edge.u == u) {
                int v = edge.v;
                if (dist[u] != INF && dist[u] + edge.weight < dist[v]) {
                    dist[v] = dist[u] + edge.weight;
                    if (!inQueue[v]) {
                        q.push(v);
                        inQueue[v] = 1;
                        count[v]++;
                        if (count[v] > N) {
                            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 = spfa(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;
}