#include<fstream.h>
#define N 50001
#define M 1500000
typedef struct nod
{long cost,info;
struct nod *urm;}Nod,*list;
typedef list graf[N];
graf g;
list r;
long m,k,d[N],co,n,i,j,t,l,*q,p=0,u=0;
void push(list &r,long x,long co)
{Nod *c=new Nod;
c->info=x;
c->cost=co;
c->urm=r;
r=c;}
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;}
for(k=1;k<=m;k++)
     {f>>l>>j>>co;
     push(g[l],j,co);}
q=(long*)malloc(3*M*sizeof(long));
d[1]=0,q[u++]=1;
while(p!=u)
     {t=q[p++];
     for(r=g[t];r!=NULL;r=r->urm)
     if(d[r->info]>d[t]+r->cost)
            {d[r->info]=d[t]+r->cost;
            q[u++]=r->info;}
     else
            if(d[r->info]>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]<<" ";
f.close();
h.close();
return 0;}