#include<stdio.h>
#define N 50001
#define M 15000001
typedef struct nod
{long c,v;
struct nod *urm;}Nod,*list;
typedef list graf[N];
graf g;
list r;
long m,k,d[N],co,n,i,j,p=0,t,l,q[M],u=0;
void push(list &r,long x,long co)
{Nod *l=new Nod;
l->v=x;
l->c=co;
l->urm=r;
r=l;}
int main()
{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\n",&l,&j,&co);
     push(g[l],j,co);}
d[1]=0;
q[u++]=1;
while(p!=u)
     {t=q[p++];
     for(r=g[t];r!=NULL;r=r->urm)
     if(d[r->v]>d[t]+r->c)
            d[r->v]=d[t]+r->c,q[u++]=r->v;
     else
            if(d[r->v]>0&&d[t]<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;}