#include <iostream>
#include <cstdio>
using namespace std;

const int N = 50001;
const int M = 250001;
const int INF = 1e9;

int vf[M], urm[M], cost[M], lst[N], q[N+2], d[N], nrq[N];
bool inq[N];
int n, nr, st, dr=-1;

void adauga(int x, int y, int c){
    vf[++nr] = y;
    cost[nr] = c;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void adauga_q(int x){
    nrq[x]++;
    if(inq[x] == true)
        return;
    if(dr == N+1)
        dr = 0;
    else
        dr++;
    q[dr] = x;
    inq[x] = true;
}

int bellman_ford(int x0){
    for(int i=1; i<=n; i++)
        d[i] = INF;

    adauga_q(x0);
    d[x0] = 0;
    while(dr != st-1){
        int node = q[st++];
        inq[node] = false;
        for(int p=lst[node]; p!=0; p=urm[p]){
            int next = vf[p];
            int c = cost[p];
            if(d[node] + c < d[next]){
                d[next] = d[node] + c;
                adauga_q(next);
                if(nrq[next] == n)
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    FILE *fin, *fout;
    int m,i,x,y,c;
    fin = fopen("bellmanford.in","r");
    fout = fopen("bellmanford.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=0; i<m; i++){
        fscanf(fin,"%d %d %d",&x,&y,&c);
        adauga(x,y,c);
    }
    if(bellman_ford(1)){
        for(i=2; i<=n; i++)
            fprintf(fout,"%d ",d[i]);
    }
    else
        fprintf(fout,"Ciclu negativ!");
    fclose(fin);
    fclose(fout);
    return 0;
}