#include <stdio.h>
#define N 50001
#define M 250001
#define st(x) 2*(x)
#define dr(x) 2*(x)+1
#define pr(x) (x)/2
long n,m;
long p[N];
struct vecin
{long cost;
 long urm;
 long nod;
}v[2*M];
long vv;

struct heap
{long nod;
 long cost;
}h[N];
long vh;

long pheap[N];
long cost[N];
int flagn[N];
int flagf[N];

void adauga_muchie(long a,long b,long c)
{vv++;
 v[vv].urm=p[a];
 p[a]=vv;
 v[vv].nod=b;
 v[vv].cost=c;
}

void adauga_heap(long nod,long cost)
{vh++;
 long i;
 struct heap aux;
 h[vh].nod=nod;
 h[vh].cost=cost;
 for (i=vh;h[i].cost<h[pr(i)].cost;i=pr(i))
 {aux=h[vh];
  h[vh]=h[pr(i)];
  h[pr(i)]=aux;
  pheap[h[i].nod]=i;
 }
 pheap[h[i].nod]=i;
}

void adauga_vecini(long a)
{long q,i;
 heap aux;
 for (q=p[a];q;q=v[q].urm)
 {if(flagf[v[q].nod]==0)
  {if(flagn[v[q].nod]==0)
   {adauga_heap(v[q].nod,v[q].cost+cost[a]);
    flagf[v[q].nod]=1;
   }
  }
  else
  {if(h[pheap[v[q].nod]].cost>cost[a]+v[q].cost)
   {h[pheap[v[q].nod]].cost=cost[a]+v[q].cost;
    for (i=pheap[v[q].nod];h[i].cost<h[pr(i)].cost;i=pr(i))
    {aux=h[vh];
     h[vh]=h[pr(i)];
     h[pr(i)]=aux;
     pheap[h[i].nod]=i;
    }
    pheap[h[i].nod]=i;
   }
  }
 }
}

void sift(long k)
{long min=k;
 heap aux;
 if(st(k)<=vh&&h[st(k)].cost<h[k].cost)
 {min=st(k);
 }
 if(dr(k)<=vh&&h[dr(k)].cost<h[min].cost)
 {min=dr(k);
 }
 if(min!=k)
 {
  aux=h[k];
  h[k]=h[min];
  h[min]=aux;
  pheap[h[k].nod]=k;
  pheap[h[min].nod]=min;
 }
}

long scoate_minim()
{pheap[h[1].nod]=0;
 h[1]=h[vh];
 pheap[h[1].nod]=1;
 vh--;
 sift(1);
}
int main ()
{long a,b,c,i;
 heap min;
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for (vv=0,i=1;i<=m;i++)
 {scanf("%ld%ld%ld",&a,&b,&c);
  adauga_muchie(a,b,c);
 }

 flagn[1]=1;
 cost[1]=0;
 adauga_vecini(1);
 for (i=1;i<=n-1;i++)
 {min=h[1];
  cost[min.nod]=min.cost;
  flagf[min.nod]=0;
  flagn[min.nod]=1;
  scoate_minim();
  adauga_vecini(min.nod);
 }
 
 for (i=2;i<=n;i++)
 {printf("%ld ",cost[i]);
 }
 
 return 0;
}