#include<bits/stdc++.h>
using namespace std;

struct Edge
{
    int v, w;
};

const int INF = 2e9;
vector<vector<Edge>> adj;
vector<int> dist;

bool bellmanford(int s, int n) {
    dist[s] = 0;
    queue<int> q;

    for (int i = 1; i <= n; i++)
        q.push(i);

    vector<bool> vis(n + 1, false);

    for (int i = 1; i <= n - 1; i++) {
        vis.assign(n + 1, false);
        bool changed = false;
        int m = q.size();
        for (int  i = 0; i < m; i++) {
            int u = q.front(); q.pop();
            for (auto ed : adj[u]) {
                int v = ed.v, w = ed.w;
                if (dist[u] != INF && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    changed = true;
                    if (!vis[v]) {
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
        if (!changed) return true;
    }

    int m = q.size();
    for (int i = 0; i < m; i++) {
        int u = q.front(); q.pop();
        for (auto ed : adj[u]) {
            int v = ed.v, w = ed.w;
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    dist.assign(n + 1, INF);
    adj.assign(n + 1, vector<Edge>());

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

    if (bellmanford(1, n)) {
        for (int i = 2; i <= n; i++)
            cout << dist[i] << " ";
    }
    else
        cout << "Ciclu negativ!";

    return 0;
}