#include<stdio.h>
#include<stdlib.h>
#define N 50001
typedef struct nod2
{long info2;
int cost;
struct nod2 *urm;}Nod2,*list;
typedef list graf[N];

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

int main()
{long n,m,i,j,k,d[N],co;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
graf g;
list r;
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
      {d[i]=N;
      g[i]=NULL;}
for(k=1;k<=m;k++)
      {scanf("%ld%ld%d",&i,&j,&co);
      push2(g[i],j,co);}
d[1]=0;
for(i=1;i<=n;i++)
      {for(r=g[i];r!=NULL;r=r->urm)
      if(d[r->info2]>d[i]+r->cost)
            d[r->info2]=d[i]+r->cost;
      else
            if((d[r->info2]>0&&d[i]<0)||(d[r->info2]<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;}