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

using namespace std;
struct nod {int val;int pr;nod *urm;};
nod *v[50001];
queue <int> st;
int m,n,use[50001],ct[50001],x,y,d,prim,ultim,c,i,e[50002];
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;
 }



 c=1;
 use [1]=1;nod *t;
 st.push(1);
 while (!st.empty() && c)
 {
     for (t=v[st.front()];t!=NULL;t=t->urm)
     {
         if (ct[st.front()]+t->pr<ct[t->val]) {ct[t->val]=ct[st.front ()]+t->pr;
                                           use[t->val]++;
                                           if (e[t->val]==0) {st.push(t->val);
                                                              e[t->val]=1;}

                                           if (use[t->val]>=n) c=0;}
     }
   e[st.front ()]=0;
   st.pop();

 }
 if (c==0) fprintf (g,"Ciclu negativ!");
   else for (i=2;i<=n;i++) fprintf (g,"%d ",ct[i]);

    return 0;
}