#include<stdio.h>
#include<stdlib.h>
#define N 50001
typedef struct stack
{long st[N],sp;};
typedef struct nod
{long info,cost;
nod *urm;}Nod,*list;
typedef list graf[N];
long n,m,i,j,k,d[N],c;
graf g;
list r;
stack s;

void push(stack &s,long x)
{s.st[++s.sp]=x;}

long pop(stack &s)
{return s.st[s.sp--];}

void push2(list &r,long x,long co)
{Nod *c=new Nod;
c->info=x;
c->cost=co;
c->urm=r;
r=c;}

int main()
{freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%ld%ld\n",&n,&m);
for(i=1;i<=n;i++)
      {d[i]=N;
      g[i]=NULL;}
for(k=1;k<=m;k++)
      {scanf("%ld%ld%ld\n",&i,&j,&c);
      push2(g[i],j,c);}
s.sp=0;
push(s,1);
while(s.sp!=0)
      {i=pop(s);
      for(r=g[i];r!=NULL;r=r->urm)
      if(d[r->info]>d[i]+r->cost)
             {d[r->info]=d[i]+r->cost;
             push(s,r->info);}
      else
             if(d[r->info]>0&&d[i]<0)
                     {printf("Ciclu negativ!");
                     return 0;}}
for(k=2;k<=n;k++)
if(d[k]>0)
      printf("%ld ",d[k]%N);
else
      printf("%ld ",d[k]);
fclose(stdin);
fclose(stdout);
return 0;}