#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#define N 50001
typedef struct nod
{long info;
nod *next;}Nod,*List;
typedef struct nod2
{long info2,cost;
nod2 *urm;}Nod2,*list;
typedef list graf[N];
long n,m,i,j,k,d[N],c;
graf g;
List l;
list r;

void push(List &l,long x)
{Nod *c=new Nod;
c->info=x;
c->next=l;
l=c;}
       
long pop(List &l)
{long x=l->info;
Nod *t=l->next;
free(l);
l=t;
return x;}

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()
{fstream f1("bellmanford.in",ios::in);
fstream f2("bellmanford.out",ios::out);
l=NULL;
f1>>n>>m;
for(i=1;i<=n;i++)
      {d[i]=N;
      g[i]=NULL;}
for(k=1;k<=m;k++)
      {f1>>i>>j>>c;
      push2(g[i],j,c);}
d[1]=0;
push(l,1);
while(l!=NULL)
      {i=pop(l);
      for(r=g[i];r!=NULL;r=r->urm)
      if(d[r->info2]>d[i]+r->cost)
             {d[r->info2]=d[i]+r->cost;
             push(l,r->info2);}
      else
             if(d[r->info2]>0&&d[i]<0)
                     {f2<<"Ciclu negativ!";
                     return 0;}}
for(k=2;k<=n;k++)
if(d[k]>0)
      f2<<d[k]%N<<" ";
else
      f2<<d[k]<<" ";
f1.close();
f2.close();
return 0;}