#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 100005
#define INF 2000000005
typedef pair<int, int> ii;

int n, m, time, d[NMAX], frecv[NMAX], incoada[NMAX];
vector<ii> a[NMAX], sol;

int main(){

    queue<int> q;
    int i, j, x, y, cost;
    bool ciclu = false;
    FILE *fin, *fout;
    fin = fopen("bellmanford.in", "r");
    fout = fopen("bellmanford.out", "w");

    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=m; i++) {
        fscanf(fin, "%d %d %d", &x, &y, &j);
        a[x].push_back(ii(y, j));
    }

    for(i=1; i<=n; i++)
        d[i] = INF;

    d[1]=0;
    q.push(1);
    frecv[1] = 1;

    while(!q.empty() && !ciclu) {
        x = q.front();
        incoada[x] = false;
        q.pop();
        for(i=0; i<(int) a[x].size(); i++) {
            y = a[x][i].first;
            cost = a[x][i].second;

            if(d[y] > d[x] + cost) {
                d[y] = d[x] + cost;

                if(frecv[y] == n-1)
                    ciclu = true;
                else {
                    frecv[y]++;
                    if(!incoada[y]) {
                        incoada[y] = true;
                        q.push(y);
                    }
                }
            }
        }
    }

    if(ciclu)
        fprintf(fout, "Ciclu negativ!");
    else
        for(i=2; i<=n; i++)
            fprintf(fout, "%d ", d[i]);

    fclose(fin);
    fclose(fout);
    return 0;
}