#include<fstream.h>
#define N 50001
#define M 10000000
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()
{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>>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)
                  {h<<"Ciclu negativ!";
                  return 0;}}
for(k=2;k<=n;k++)
if(d[k]>0)
     h<<d[k]%N<<" ";
else
     h<<d[k]<<" ";
f.close();
h.close();
return 0;}