#include<fstream.h>
#define max 50001
#define inf 1999999
 ifstream f("bellmanford.in");
 ofstream g("bellmanford.out");
 long d[max],i,n,j,x,y,z,m;
typedef struct nod
{
 int a,b,dist;
 nod *urm;
} *pNod;

pNod prim;


void add(pNod &pr,int x, int y, int val)
{
 pNod m=new nod;
 m->a=x;
 m->b=y;
 m->dist=val;
 m->urm=pr;
 pr=m;
}

int ford()
{
 for(i=1;i<=n;i++)
  if(i==1) d[i]=0;
  else d[i]=inf;
 int ok=1,cont=0;
 while(ok==1&&cont<n)
 {    pNod q;
   ok=0;
   cont++;
  for(q=prim;q;q=q->urm)
  {
   if(d[q->b]>d[q->a]+q->dist)
    d[q->b]=d[q->a]+q->dist,ok=1;
  }

 }
 if(cont==n)
 {
  g<<"Ciclu negativ!";
  return 0;
 }
 return 1;
}

int main()
{
 f>>n;
 f>>m;
 for(i=1;i<=m;i++)
 {
  f>>x>>y>>z;
  add(prim,x,y,z);
 }

 x=ford();
 if(x==1)
 {
 for(i=1;i<=n;i++)
  if(d[i]==inf)
	d[i]=0;

 for(i=2;i<=n;i++)
   g<<d[i]<<" ";
 }
 return 0;
}