#include<stdio.h>
struct g
{
int nod,cost;
g *urm;       
};
int n,m;
g *a[50005];
int d[50005],t[50005],poz[50005],k;
void add(int x,int y,int z)
{
 g *p=new g;
 p->nod=y;
 p->cost=z;
 p->urm=a[x];
 a[x]=p;     
}
void dij()
{int i;
 for(i=2;i<=n;i++)
     {d[i]=1<<30;poz[i]=-1;}
 d[1]=0;
 g *t1=a[1];
 while(t1)
 {  d[t1->nod]=t1->cost;
	t[t1->nod]=1;
   t1=t1->urm;  
 }
 g *p;
 
 for(i=1;i<=n;i++)
 {if(poz[i]!=1)
 {	 
  poz[i]=1;
  p=a[i];
//  int min=1<<10;
  int nod;
//  printf("\n%d : ",i);
  while(p)
  {// printf("%d ",p->nod);
   nod=p->nod;
   if(d[p->nod]>(p->cost+d[i]))
   {d[p->nod]=(p->cost+d[i]);
    t[p->nod]=nod;
   }
   
   p=p->urm;
  }
  }
//  p=a[nod];
  
 }
 
}	 

int main()
{int x,y,z,i;
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%d %d",&n,&m);
 for(i=0;i<m;i++)
  {
   scanf("%d %d %d",&x,&y,&z);               
   add(x,y,z);
  }
 dij();   
 for(i=2;i<=n;i++)
  {
   if(d[i]==1<<30)               
    printf("0 "); 
    else
    printf("%d ",d[i]);
  }
 printf("\n");
// for(i=1;i<=n;i++)
//	 printf("%d ",t[i]); 
 return 0;
}