#include<stdio.h>
FILE*fin=fopen("dijkstra.in","r");
FILE*fout=fopen("dijkstra.out","w");
#define inf 1000000000
#define nmax 50001
int drmin[nmax],wh[nmax],h[nmax],hs,n,m;
struct nod
{
  int vec,cost;
  nod *urm;
};
nod *g[nmax];
void creeaza_muchie(int a,int b,int c)
{
  nod *q;
  q=new nod;
  q->vec=b;q->cost=c;
  q->urm=g[a];
  g[a]=q;
}
void rech(int nh)
{
  int ls=nh*2,rs=nh*2+1,min=drmin[h[nh]],nmin=nh;
  if(ls<=hs&&drmin[h[ls]]<min)
  {
    min=drmin[h[ls]];
    nmin=ls;
  }
  if(rs<=hs&&drmin[h[rs]]<min)
  {
    min=drmin[h[rs]];
    nmin=rs;
  }
  if(nmin!=nh)
  {
    h[nmin]^=h[nh]^=h[nmin]^=h[nh];
    wh[h[nh]]^=wh[h[nmin]]^=wh[h[nh]]^=wh[h[nmin]];
    rech(nmin);
  }
}
void actualizeaza(int x)
{
  int y,cy,ns,nf;
  nod *q;
  q=g[x];
  while(q)
  {
    y=q->vec;
    cy=q->cost;
    if(wh[y]&&drmin[y]>drmin[x]+cy)
    {
      drmin[y]=drmin[x]+cy;
      ns=wh[y];
      nf=ns/2;
      while(ns>1&&drmin[h[ns]]<drmin[h[nf]])
      {
	h[ns]^=h[nf]^=h[ns]^=h[nf];
	wh[h[ns]]^=wh[h[nf]]^=wh[h[ns]]^=wh[h[nf]];
	ns=nf;
	nf=ns/2;
      }
    }
    q=q->urm;
  }
}
int extragemin()
{
  int sol=h[1];
  h[1]=h[hs];
  wh[h[1]]=1;
  hs--;
  rech(1);
  return sol;
}
void dijkstra(int source)
{
  int i,x;
  for(i=1;i<=n;i++)
    drmin[i]=inf;
  drmin[source]=0;
  for(i=1;i<=n;i++)
  {
    h[i]=i;
    wh[i]=i;
  }
  hs=n;
  h[1]=source;h[source]=1;
  wh[source]=1;wh[h[source]]=source;
  for(i=1;i<n;i++)
  {
    x=extragemin();
    if(drmin[x]==inf) break;
    actualizeaza(x);
    wh[x]=0;
  }
}
int main()
{
  int i,a,b,c;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=n;i++)
    g[i]=NULL;
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d%d",&a,&b,&c);
    creeaza_muchie(a,b,c);
  }
  dijkstra(1);
  for(i=2;i<=n;i++)
    fprintf(fout,"%d ",drmin[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}