#include<stdio.h>
#define inf 300000
struct graf
{
  int nod,cost;
  graf *urm;
};
graf *a[250001];
long d[50001];
int viz[50001];
long n,m;
void add(int unde,int ce,int cat)
{
  graf *q=new graf;
  q->nod = ce;
  q->cost = cat;
  q->urm = a[unde];
  a[unde]=q;
}
void citire()
{
  FILE *in = fopen("dijkstra.in","rt");
  int x,y,z;
  fscanf(in,"%ld %ld",&n,&m);
  for(long i=1;i<=m;i++)
  {
   fscanf(in,"%d %d %d",&x,&y,&z);
   add(x,y,z);
  }
  fclose(in);
}
void dijkstra()
{
  long i,j;
  for(i=1;i<=n;i++) // initializam dist
   d[i]=inf;//de la nodul 1 la restul nodurilor cu inf
  for(graf *p=a[1];p!=NULL;p=p->urm)
   d[p->nod]=p->cost;
  int min,pmin=0;  // dist minima si nodul
  viz[1]=1;
  for(i=2;i<=n;i++)// pentru toate nodurile
  {
	 min=inf;// distanta minima initial e inf
	 for(j=1;j<=n;j++) // cautam un nod intermediar care
	  if(d[j]<min&!viz[j]) //  daca dist pana in nodul interm. < dist min
	  {                     // si nodul j nu e vizitat
	   min=d[j];// min = dist pana in j
	   pmin=j; // nodul este j
	  }
	  viz[pmin]=1;// vizitam nodul la dist minima
	  graf *t=a[pmin]; // pentru toate nodurile vecine lui pmin
	  while(t)
	  {
	   if(d[t->nod]>d[pmin]+t->cost) //daca dist pana in nodul t
	    d[t->nod] = d[pmin]+t->cost; // > dist pana in nodul aflat la dist minima + dist pana in nodul
	   t=t->urm;// vecin a lui pmin   at actualizam distanta pana in nodul vecin lui pmin
	  }
  }
}
int main()
{
  int i;
  citire();
  dijkstra();
  FILE *out=fopen("dijkstra.out","wt");
  for(i=2;i<=n;i++)
  fprintf(out,"%ld ",d[i]==inf ? 0 : d[i]);
  fclose(out);
  return 0;
}