#include<cstdio>
#define N 50001
typedef struct
{int u,v,e[1500000];}Q;
typedef struct nod
{int co,in;
nod *urm;}Nod;
Nod *g[N],*r;
Q q;
int m,d[N],c,n,i,j;

void P(Nod *&r,int x,int c)
{Nod *t=new Nod;
t->in=x,t->co=c,t->urm=r,r=t;}

int main()
{freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
     d[i]=N;
while(m--)
     scanf("%d%d%d",&i,&j,&c),P(g[i],j,c);
d[1]=0,q.e[q.v++]=1;
while(q.u<q.v)
     {j=q.e[q.u++];
     for(r=g[j];r;r=r->urm)
     if(d[r->in]>d[j]+r->co)
            d[r->in]=d[j]+r->co,q.e[q.v++]=r->in;
     else
            if(d[r->in]>0&&d[j]<0)
                  {printf("Ciclu negativ!");
                  return 0;}}
for(i=2;i<=n;i++)
     printf("%d ",d[i]>0?(d[i]%N):d[i]);
return 0;}