#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
const int oo = 1<<29;
 
int main() {
    ios::sync_with_stdio(false);
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adjl(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adjl[u].emplace_back(w, v);
    }
 
    vector<int> dist(n, oo);
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    vector<bool> inq(n);
    inq[0] = true;
    vector<int> ninq(n);
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
 
        for(auto e: adjl[u]) {
            int v = e.second;
            int w = e.first;
            if (dist[v] > dist[u]+w) {
                dist[v] = dist[u]+w;
                ninq[v] = ninq[u]+1;
                if (!inq[v]) {
                    if (ninq[v] == n) {
                        puts("Ciclu negativ!");
                        return 0;
                    }
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
 
    for (int i = 1; i < n; i++) {
        printf("%d%s", dist[i], i < n-1 ? " " : "\n");
    }
    return 0;
}