#include<stdio.h>
#define inf 30000
struct graf
{
  int nod,cost;
  graf *urm;
};
graf *a[5001];
int d[5001],viz[5001];
int 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 i,x,y,z;
  fscanf(in,"%d %d",&n,&m);
  for(i=1;i<=n;i++)
  {
   fscanf(in,"%d %d %d",&x,&y,&z);
   add(x,y,z);
  }
  fclose(in);
}
void dijkstra()
{
  int i,j;
  for(i=2;i<=n;i++) // initializam dist
   d[i]=inf;//de la nodul 1 la restul nodurilor cu inf
  int min,pmin=0; // dist minima si nodul
  for(i=1;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,"%d ",d[i]==inf ? 0 : d[i]);
  fclose(out);
  return 0;
}