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

bitset <N+1> enqueue;
vector <pair <int, int>> G[N+1];
int dist[N+1], ct[N+1];

int main () {
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");

    int n, m;
    fin >> n >> m;

    int i, j, c;
    for (; m; m--) {
        fin >> i >> j >> c;
        G[i].push_back(make_pair(j, c));
    }

    fill(&dist[2], &dist[n+1], INF);
    queue <int> Q;

    Q.push(1);
    enqueue[1]=ct[1]=1;

    while (!Q.empty()) {
        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;
                Q.push(it.first);

                enqueue[it.first]=1;
                ++ct[it.first];

                if (ct[it.first]==n) {
                    fout << "Ciclu negativ!";
                    exit(0);
                }
            }
    }

    for (i=2; i<=n; ++i)
        fout << dist[i] << ' ';
    return 0;
}