#include<fstream.h>
#define N 50001
#define M 1500000
typedef struct
{long u,v,e[M];}qu;
typedef struct nod
{long co,in;
nod *urm;}Nod;
Nod *g[N],*r;
qu q;
long m,d[N],c,n,i,j;

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

int main()
{q.u=q.v=0;
ifstream f("bellmanford.in");
ofstream h("bellmanford.out");
f>>n>>m;
for(i=1;i<=n;i++)
     d[i]=N,g[i]=NULL;
while(m--)
     f>>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)
                  {h<<"Ciclu negativ!";
                  return 0;}}
for(i=2;i<=n;i++)
if(d[i]>0)
     h<<d[i]%N<<" ";
else
     h<<d[i]<<" ";
return 0;}