#include <bits/stdc++.h>
#define N 50001
#define INF 0x3F3F3F3F
using namespace std;

array <vector <pair <int, int>>, N> G;
bitset <N> enqueue;
queue <int> Q;
array <int, N> dist, qcont;
int main () {
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");
    int n, m, i, j, c;
    fin >> n >> m;
    for (; m; m--) {
        fin >> i >> j >> c;
        G[i].emplace_back(make_pair(j, c));
    }

    bool stop=0;
    dist.fill(INF);
    dist[1]=0;
    Q.push(1);
    enqueue[1]=1;
    while (!Q.empty() && !stop) {
        auto save=Q.front();
        Q.pop();
        enqueue[save]=0;
        for (auto it: G[save])
            if (dist[it.first]>dist[save]+it.second) {
                dist[it.first]=dist[save]+it.second;
                if (!enqueue[it.first])
                    if (Q.size()>n)
                        stop=1;
                    else {
                        Q.push(it.first);
                        enqueue[it.first]=1;
                        qcont[it.first]++;
                    }
            }
    }

    if (stop)
        fout << "Ciclu negativ!" << endl;
    else
        for (i=2; i<=n; i++)
            fout << dist[i] << ' ';
    return 0;
}