#include <bits/stdc++.h>

using namespace std;

struct nod{
    int y, c;
};

vector<nod> v[50005];
int viz[50005];
int d[50005];
int cnt[50005];

priority_queue<int> q;

int main()
{
    int n, m, x;
    FILE *f = fopen("bellmanford.in", "r");
    FILE *g = fopen("bellmanford.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        nod a;
        fscanf(f, "%d %d %d", &x, &a.y, &a.c);
        v[x].push_back(a);
    }

    for(int i = 2; i <= n; i ++)
        d[i] = 2147483647;
    q.push(1);
    viz[1] = true;
    bool cneg = false;
    while(!q.empty() && !cneg) {
        int in = q.top();
        q.pop();
        viz[in] = false;
        for(int i = 0; i < v[in].size(); i ++) {
            int j = v[in][i].y;
            if(v[in][i].c + d[in] < d[j]) {
                if(cnt[j] > n) {
                    cneg = true;
                }
                else {
                    d[j] = d[in] + v[in][i].c;
                    if(!viz[j])
                        q.push(j);
                    viz[j] = true;
                    cnt[j] ++;
                }
            }
        }
    }
    if(!cneg) {
        for(int i = 2; i <= n; i ++) {
            fprintf(g, "%d ", d[i]);
        }
    }
    else fprintf(g, "Ciclu negativ!");
    fprintf(g, "\n");
    return 0;
}