#include<stdio.h>
#include<stdlib.h>
#define N 50001
#define M 1500000
typedef struct s
{long prim,ultim,nel,elem[M];}queue;
typedef struct nod
{long co,in;
struct nod *urm;}Nod,*list;
typedef list graf[N];
graf g;
list r;
queue q;
long m,k,d[N],c,n,i,j,p,t,l;

void addQ(queue &q,long x)
{q.nel++,q.elem[q.ultim++]=x;}

long delQ(queue &q)
{q.nel--,q.prim++;
return q.elem[q.prim-1];}

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

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