#include <stdio.h>
FILE *f,*g;

using namespace std;
struct nod {int val;int pr;nod *urm;};
nod *v[50001];
int m,n,use[50001],ct[50001],x,y,d,prim,ultim,st[50001],c,i;
void add (int x,int y,int d)
{
    nod *t;
    t=new nod;
    t->val=y;
    t->pr=d;
    t->urm=v[x];
    v[x]=t;
}
int main()
{f=fopen ("bellmanford.in","r");
 g=fopen ("bellmanford.out","w");
 fscanf (f,"%d%d",&n,&m);
 for (i=1;i<=m;i++)
 {
     fscanf (f,"%d%d%d",&x,&y,&d);
     add (x,y,d);
 }
 for (i=2;i<=n;i++)
 {
     ct[i]=0x3f3f3f3f;
 }
 st[1]=1;
 prim=1;
 ultim=1;
 c=1;
 use [1]=1;nod *t;
 while (prim <=ultim && c)
 {
     for (t=v[st[prim]];t!=NULL;t=t->urm)
     {
         if (ct[st[prim]]+t->pr<ct[t->val]) {ct[t->val]=ct[st[prim]]+t->pr;
                                           use[t->val]++;
                                           st[++ultim]=t->val;
                                           if (use[t->val]>=n) c=0;}
     }
   prim ++;
 }
 if (c==0) fprintf (g,"Ciclu negativ!");
   else for (i=2;i<=n;i++) fprintf (g,"%d ",ct[i]);

    return 0;
}