#include <stdio.h>
FILE *g=fopen("dijkstra.out","w");
#define NMAX 50001
#define inf 1<<30
typedef struct nodul
 {
 int cost,nod;
 nodul *urm;
 } graf;
graf *A[NMAX];
int n,h[NMAX],poz[NMAX],k;
long d[NMAX];
void swap(int &x,int &y)
 {
 int ax=x;
 x=y;
 y=ax;
 }
void add(int x,int y,int c)
 {
 graf *aux=new graf; 
 aux->cost=c;
 aux->nod=y;
 aux->urm=A[x];
 A[x]=aux;
 }
void read()
 {
 int m,x,y,c,i;
 FILE *f=fopen("dijkstra.in","r");
 fscanf(f,"%d %d",&n,&m);
 for(i=2;i<=n;i++) d[i]=inf;
 for(i=0;i<m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&c);
  add(x,y,c);
  }
 }
void upheap(int nod)
 {
 int t;
 while(nod>1)
  {
  t=nod>>1;
  if(d[h[t]]>d[h[nod]])
   {
   swap(h[t],h[nod]);
   poz[h[t]]=t;
   poz[h[nod]]=nod;
   }
  else
   return;
  nod=t;
  }
 }
void downheap(int nod)
 {
 int fiu;
 while(2*nod<=k)
  {
  fiu=2*nod;
  if(fiu+1<=k&&d[h[fiu+1]]<d[h[fiu]])
   ++fiu;
  if(d[h[nod]]>d[h[fiu]])
   {
   swap(h[nod],h[fiu]);
   poz[h[nod]]=nod;
   poz[h[fiu]]=fiu;
   }
  else
   break;
  }
 }
void dijkstra()
 {
 int x;
 h[++k]=1;
 poz[h[k]]=k;;
 while(k)
  {
  x=h[1];
  swap(h[1],h[k]);
  poz[h[1]]=1;
  poz[h[k]]=0;
  k--;
  downheap(1);
  
  graf *p=A[x];
  while(p)
   {
   if(d[p->nod]>d[x]+p->cost)
    {
	d[p->nod]=d[x]+p->cost;
    if(h[poz[p->nod]])
	 upheap(poz[p->nod]);
	else
	 {
	 h[++k]=p->nod;
	 poz[h[k]]=k;
	 upheap(k);
	 }
    }
   p=p->urm;
   }
  }
 }
void show()
 {
 int i;
 FILE *g=fopen("dijkstra.out","w");
 for(i=2;i<=n;i++)
  fprintf(g,"%ld ",d[i]);
 }
int main()
 {
 read();
 dijkstra();
 show();
 }