#include <bits/stdc++.h>

using namespace std;
const int N = 5e4, inf = 2e9;
int d[N + 5], cnt[N + 5];
vector <pair <int, int>> g[N + 5];
bool inq[N + 5];

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, m, u, v, w;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> u >> v >> w,
        g[u].emplace_back(v, w);
    queue <int> q;
    fill(d + 2, d + n + 1, inf);
    for(q.push(1); !q.empty(); q.pop()) {
        int u = q.front();
        inq[u] = false;
        for(auto [v, w] : g[u]) if(d[v] > d[u] + w) {
            d[v] = d[u] + w;
            if(!inq[v]) {
                q.push(v);
                if(++cnt[v] == n) {
                    cout << "Ciclu negativ!";
                    return 0;
                }
                inq[v] = true;
            }
        }
    }
    for(int i = 2; i <= n; i++)
        cout << d[i] << " ";
    return 0;
}