#include <iostream>
#include <cstdio>
#define INF 1e9
using namespace std;
const int EMAX = 250001;
const int NMAX = 50001;
struct{
    int nod1, nod2, w;
}muchii[EMAX];
int distante[NMAX];
int main()
{
    FILE *fin, *fout;
    int n,m,i,e,x,y,cost,circneg;
    fin=fopen("bellmanford.in","r");
    fout=fopen("bellmanford.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=n;i++)
        distante[i] = INF;
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d %d\n",&x,&y,&cost);
        muchii[i].nod1 = x;
        muchii[i].nod2 = y;
        muchii[i].w = cost;
    }
    distante[1] = 0;
    for(i=1;i<=n-1;i++)
        for(e=1;e<=m;e++)
            if(distante[muchii[e].nod1] + muchii[e].w < distante[muchii[e].nod2])
                distante[muchii[e].nod2] = distante[muchii[e].nod1] + muchii[e].w;
    circneg = 0;
    for(e=1;e<=m && !circneg;e++)
        if(distante[muchii[e].nod1] + muchii[e].w < distante[muchii[e].nod2])
            circneg = 1;
    if(circneg == 1)
        fprintf(fout,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            fprintf(fout,"%d ",distante[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}