#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
const long long INF = 1e15;

struct Edge {
    int to;
    int cost;
};

int main() {
    int n, m;
    fin >> n >> m;

    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        adj[u].push_back({v, c});
    }

    vector<long long> dist(n + 1, INF);
    vector<int> cnt(n + 1, 0);
    vector<bool> in_queue(n + 1, false);

    queue<int> q;
    dist[1] = 0;
    q.push(1);
    in_queue[1] = true;

    bool negative_cycle = false;

    while (!q.empty() && !negative_cycle) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (auto &edge : adj[u]) {
            int v = edge.to;
            int cost = edge.cost;
            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                    cnt[v]++;
                    if (cnt[v] > n) {
                        negative_cycle = true;
                        break;
                    }
                }
            }
        }
    }

    if (negative_cycle) {
        fout << "Ciclu negativ!\n";
    } else {
        for (int i = 2; i <= n; i++) {
            if (dist[i] == INF) fout << 0 << " ";
            else fout << dist[i] << " ";
        }
        fout << "\n";
    }

    return 0;
}