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

const int oo = INT_MAX / 2;
vector<pair<int, int>> adj[50005]; // adj[u] = {v, cost}

bool spfa(int n, int source, vector<int>& dist) {
    dist.assign(n + 1, oo);
    vector<bool> inQueue(n + 1, false);
    vector<int> count(n + 1, 0); // număr relaxări

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

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

        for (auto it: adj[u]) {
            int v = it.first;
            int w = it.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    if (count[v] > n) {
                        // Ciclul negativ detectat
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }

    vector<int> dist;
    bool ok = spfa(n, 1, dist);

    if (!ok) {
        cout << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= n; ++i)
            cout << dist[i] << ' ';
    }
    return 0;
}