#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

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

const int NMAX = 50005;
const int INF = 1e9;

struct Edge {
    int x, y, w;
};

int n, m, cost[NMAX];
vector<Edge> edges;
bool inQueue[NMAX];

void bellmanFord() {
    // Initialization
    fill(cost, cost + n + 1, INF);
    cost[1] = 0;
    queue<int> q;
    q.push(1);
    inQueue[1] = true;

    int step = 0;
    while (!q.empty() && step <= n) {  // At most n steps to avoid unnecessary processing
        int size = q.size();
        while (size--) {
            int node = q.front();
            q.pop();
            inQueue[node] = false;

            for (const auto& edge : edges) {
                if (edge.x == node && cost[node] + edge.w < cost[edge.y]) {
                    cost[edge.y] = cost[node] + edge.w;
                    if (!inQueue[edge.y]) {
                        q.push(edge.y);
                        inQueue[edge.y] = true;
                    }
                }
            }
        }
        step++;
    }

    // Negative cycle check
    for (const auto& edge : edges) {
        if (cost[edge.x] + edge.w < cost[edge.y]) {
            out << "Ciclu negativ!";
            return;
        }
    }

    for (int i = 2; i <= n; ++i) {
        out << (cost[i] == INF ? "INF" : to_string(cost[i])) << " ";
    }
}

int main() {
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        in >> a >> b >> c;
        edges.push_back({a, b, c});
    }

    bellmanFord();
    return 0;
}