#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;
}

void ford()
{
 for(i=1;i<=n;i++)
  if(i==1) d[i]=0;
  else d[i]=inf;
 int ok=1;
 while(ok==1)
 {    pNod q;
   ok=0;
  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;
  }
 }
}

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

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

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

 return 0;
}