//Dijkstra pe heap.
#include <stdio.h>    
const int inf=1<<30;  
struct graf  
{  
  int nod,cost;  
  graf *next;  
};  
   
int n,m;  
graf *a[50002];  
int d[50002],h[50002],poz[50002],k;  
   
void add(int x,int y,int z) //unde,ce,cost 
{  
  graf *q=new graf;  
  q->nod=y;  
  q->cost=z;  
  q->next=a[x];  
  a[x]=q;  
}  
   
void citire()  
{  
  freopen("dijkstra.in","r",stdin);
  scanf("%d %d",&n,&m);  
  int x,y,z;  
  for (int i=1;i<=m;i++)  
  {  
    scanf("%d %d %d",&x,&y,&z);  
    add(x,y,z);  
  }  
}  
   
void interschimb(int x,int y) {int t=h[x];h[x]=h[y];h[y]=t;}  
   
void heap_urcare(int x)  
{  
  int tata;  
  while (x>1)  
  {  
    tata=x/2;  
    if (d[h[tata]]>d[h[x]])  
    {  
      poz[h[x]]=tata;  
      poz[h[tata]]=x;  
      interschimb(tata,x);  
      x=tata;  
    }  
    else  
      x=1;  
  }  
}  
   
void heap_coborare(int x)  
{  
  int f;  
  while(x<=k)  
  {  
    f=x;  
    if ((x*2)<=k)  
    {  
      f=x*2;  
      if (f+1<=k)  
        if (d[h[f+1]]<d[h[f]]) f++;  
    }  
    else return;  
    if (d[h[x]]>d[h[f]])  
    {  
      poz[h[x]]=f;  
      poz[h[f]]=x;  
      interschimb(x,f);  
      x=f;  
    }  
    else return;  
  }  
}  
   
void dijkstra()  
{  
  for (int i=2;i<=n;i++)
  {  
    d[i]=inf;
    poz[i]=(-1);
  }  
  poz[1]=1;  
  h[k++] = 1;  
  while (k)  
  {  
    int min=h[1];  
    interschimb(1,k);  
    poz[h[1]]=1;  
    k--;  
    heap_coborare(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)  
          heap_urcare(poz[q->nod]);  
        else  
        {  
           h[k++]=q->nod;  
           poz[h[k]]=k;  
           heap_urcare(k);  
        }  
      }  
      q=q->next;  
    }  
  }  
}  
   
int main()  
{  
  citire();  
  dijkstra();
  freopen("dijkstra.out","w",stdout)   
  for (int i=2;i<=n;i++) 
  {
    if (d[i]!=inf) printf("%d ",d[i])
    else printf("0 ");  
  }  
  return 0;  
}