#include <stdio.h>
#define nmax 50001
#define inf 1<<30
typedef struct nod
 {
 int x,c;
 nod *urm;
 } lista;
lista *l[nmax];
int poz[nmax],h[nmax],nh;
long d[nmax];
int n;
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
void add(int x,int y,int cost)
 {
 lista *p=new lista;
 p->x=y;
 p->c=cost;
 p->urm=l[x];
 l[x]=p;
 }
void swap(int a,int b)
 {
 int c=h[a];
 h[a]=h[b];
 h[b]=c;
 poz[h[a]]=a;
 poz[h[b]]=b;
 }
void upheap(int nod)
 {
 if(nod<=1) return;
 int i=nod>>1;
 if(d[h[i]]>d[h[nod]])
  {
  swap(i,nod);
  upheap(i);  
  }
 }
void downheap(int nod)
 {
 int i=nod<<1;
 if(i<=nh)
  {
  if(i+1<=nh&&d[h[i+1]]<d[h[i]])
   ++i;
  if(d[h[i]]<d[h[nod]])
   {
   swap(i,nod);
   downheap(i);
   }
  }
 }
void read()
 {
 int i,m,x,y,c;
 fscanf(f,"%d %d",&n,&m);
 for(i=0;i<m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&c);
  add(x,y,c);
  }
 fclose(f);
 d[1]=0;
 for(i=2;i<=n;i++)d[i]=inf;
 }
void solve()
 {
 int nod;
 lista *p;
 for(p=l[1];p!=NULL;p=p->urm)
  {
  d[p->x]=p->c;
  h[++nh]=p->x;
  poz[h[nh]]=nh;
  upheap(nh);
  }
 while(nh)
  {
  nod=h[1];
  swap(1,nh);
  --nh;
  downheap(1);
  for(p=l[nod];p!=NULL;p=p->urm)
   {
   if(d[p->x]>d[nod]+p->c)
    {
    d[p->x]=d[nod]+p->c;
	if(poz[p->x])
	 upheap(poz[p->x]);
	else
	 {
	 h[++nh]=p->x;
	 poz[h[nh]]=nh;
	 upheap(nh);
	 }
    }
   }
  }
 }
void show()
 {
 for(int i=2;i<=n;i++)
  {
  if(d[i]==inf)
   fprintf(g,"0 ");
  else
   fprintf(g,"%ld ",d[i]);
  }
 fclose(g);
 }
int main()
 {
 read();
 solve();
 show();
 return 0;
 }