#include<fstream.h>
#define N 50001
typedef struct
{long pr,ul,el[3*N];}qu;
typedef struct nod
{long co,in;
struct nod *urm;}Nod;
Nod *g[N],*r;
qu q;
long m,k,d[N],c,n,i,j,p,t,l;

void aQ(qu &q,long x)
{q.el[q.ul++]=x;}

long dQ(qu &q)
{return q.el[q.pr++];}

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

int main()
{q.pr=q.ul=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>>l>>j>>c,push(g[l],j,c);
d[1]=0,aQ(q,1);
while(q.pr<q.ul)
     {t=dQ(q);
     for(r=g[t];r;r=r->urm)
     if(d[r->in]>d[t]+r->co)
            d[r->in]=d[t]+r->co,aQ(q,r->in);
     else
            if(d[r->in]>0&&d[t]<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;}