#include <stdio.h>
struct graf
{
 int nod,cost;
 graf *next;
};
graf *a[50001];
int n,m,x,y,c,h[50001],poz[50001],k=1,min,d[50001];
void swap(int &a,int &b)
{
 int aux=a;
 a=b;
 b=aux;
}
void downheap(int w)
{
 int f;
 while (w<=k)
 {
  if (2*w<=k)
  {
   f=2*w;
   if (f+1<=k&&d[f+1]>d[f])
    f++;
  }
  else
   return;
  if (d[f]>d[w])
  {
   poz[h[w]]=f;
   poz[h[f]]=w;
   swap(h[w],h[f]);
   w=f;
  }
  else
   return;
 }
}
void upheap(int w)
{
 int t;
 while (w>1)
 {
  t=w/2;
  if (d[t]<d[w])
  {
   poz[h[w]]=t;
   poz[h[t]]=w;
   swap(h[w],h[t]);
   w=t;
  }
  else
   return;
 }
}
int main()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%d %d\n",&n,&m);
 int i;
 for (i=0;i<m;i++)
 {
  scanf("%d %d %d\n",&x,&y,&c);
  graf *q=new graf;
  q->nod=y;
  q->cost=c;
  q->next=a[x];
  a[x]=q;
 }
 for (i=1;i<=n;i++)
 {
  poz[i]=-1;
  d[i]=51000000;
 }
 d[1]=0;
 h[1]=1;
 poz[1]=1;
 while (k)
 {
  min=h[1];
  swap(h[1],h[k]);
  poz[h[1]]=1;
  k--;
  downheap(1);
  graf *q=a[min];
  while (q)
  {
   if (d[q->nod]>d[min]+q->cost)
   {
    d[q->nod]=d[min]+q->cost;
    if (poz[q->nod]!=-1)
     upheap(poz[q->nod]);
    else
    {
     k++;
     poz[q->nod]=k;
     h[k]=q->nod;
     upheap(k);
    }
   }
   q=q->next;
  }
 }
 for (i=2;i<=n;i++)
  printf("%d ",d[i]<51000000 ? d[i] : 0);
 return 0;
}