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

using namespace std;

const int N_MAX = 50000 + 1;
const int INF = 1<<30;

struct muchie {
    int nod, cost;
};

int main() {
    // Step 1: initialize graph
    ifstream fin("bellmanford.in");

    int N, M;
    fin >> N >> M;

    vector<muchie> muchii[N_MAX];
    for (int i = 0, x, y, c; i < M; i++) {
        fin >> x >> y >> c;
        muchii[x].push_back({y, c});
    }

    // Step 2: relax edges repeatedly
    vector<int> dist(N_MAX, INF), cnt_in_coada(N_MAX, 0);
    queue<int> q;
    bool ciclu_negativ = false;
    q.push(1); dist[1] = 0;
    while (!q.empty() && !ciclu_negativ) {
        int v = q.front(); q.pop();
        if (dist[v] == INF) continue;

        for (auto it: muchii[v]) {
            int c = it.cost, u = it.nod;
            if (dist[v] + c < dist[u]) {
                dist[u] = dist[v] + c;
                if (cnt_in_coada[u] > N) {
                    ciclu_negativ = true;
                    break;
                } else {
                    cnt_in_coada[u]++;
                    q.push(u);
                }
            }
        }
    }

    ofstream fout("bellmanford.out");
    if (ciclu_negativ) {
        fout << "Ciclu negativ!";
    } else {
        for (int v = 2; v <= N; v++) {
            fout << dist[v] << " ";
        }
    }

    return 0;
}