#include<stdio.h>
#include<stdlib.h>
#define N 50001
#define M 25000001
typedef struct s
{long prim,ultim;
unsigned int nel,elem[M];}queue;
typedef struct nod
{unsigned int info;
long cost;
struct nod *urm;}Nod,*list;
typedef list graf[N];
graf g;
list r;
queue q;

void addQ(queue &q,unsigned int x)
{q.nel++;
q.elem[q.ultim++]=x;}
       
unsigned int delQ(queue &q)
{q.nel--;
q.prim++;
return q.elem[q.prim-1];}

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

int main()
{long m,k,d[N],co;
unsigned int n,i,j;
q.nel=q.prim=q.ultim=0;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%u%ld",&n,&m);
for(i=1;i<=n;i++)
      {d[i]=N;
      g[i]=NULL;}
for(k=1;k<=m;k++)
      {scanf("%u%u%ld",&i,&j,&co);
      push(g[i],j,co);}
d[1]=0;
addQ(q,1);
while(q.nel!=0)
      {i=delQ(q);
      for(r=g[i];r!=NULL;r=r->urm)
      if(d[r->info]>d[i]+r->cost)
            {d[r->info]=d[i]+r->cost;
            addQ(q,r->info);}
      else
            if(d[r->info]>0&&d[i]<0)
                    {printf("Ciclu negativ!");
                    return 0;}}
for(i=2;i<=n;i++)
if(d[i]>0)
      printf("%ld ",d[i]%N);
else
      printf("%ld ",d[i]);
fclose(stdin);
fclose(stdout);
return 0;}