#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define maxn 50005
#define infinit 1<<30
struct graf
    {   int nod,cost;   };
struct graf *a[maxn];
int in_coada[maxn],gd[maxn],d[maxn];
int *coada;
int n;

    void citire(void)
    {   FILE *fin=fopen("bellmanford.in","r");
        int m,x,y,c;
        fscanf(fin,"%d%d",&n,&m);
        for(;m;m--)
        {   fscanf(fin,"%d%d%d",&x,&y,&c);
            a[x]=(graf*)realloc(a[x], (gd[x]+1)*sizeof(graf));
            a[x][gd[x]].cost=c; a[x][gd[x]].nod=y;
            gd[x]++;
        }
        fclose(fin);
    }

    int bellmanford(void)
    {   graf y;
        int k,x,prim,ultim;

        prim=ultim=0;
        coada=(int*)realloc(coada,(prim+1)*sizeof(int));
        coada[prim]=1;
        in_coada[1]=1; d[1]=0;

        for(k=2;k<=n;k++) d[k]=infinit;

        while(prim<=ultim)
        {   x=coada[prim++];
            for(k=0;k<gd[x];k++)
            {   y=a[x][k];
                if(d[y.nod]>d[x]+y.cost)
                {   d[y.nod]=d[x]+y.cost;
                    ultim++;
                    coada=(int*)realloc(coada, (ultim+1)*sizeof(int));
                    coada[ultim]=y.nod;
                    in_coada[y.nod]++;
                }
                if(in_coada[y.nod]>=n) return 0;
            }
        }
        return 1;
    }

    void afisare(void)
    {   FILE *fout=fopen("bellmanford.out","w");
        if(bellmanford()) for(int k=2;k<=n;k++) fprintf(fout,"%d ",(d[k]!=infinit ? d[k]:0));
        else fprintf(fout,"Ciclu negativ!");
        fclose(fout);
    }

int main(void)
{   citire();
    afisare();
    return 0;
}