#include<stdio.h>
FILE*fin=fopen("dijkstra.in","r");
FILE*fout=fopen("dijkstra.out","w");
#define maxn 50001
#define inf 1000000000
struct nod{int sp;int cost;nod*urm;};
nod *vec[maxn],*q;
int p[maxn],u[maxn],sph[maxn],heap[maxn],n,m;
void rec(int ndc,int dim)
{
  int nd=ndc,min=p[heap[ndc]],st,dr,val;
  st=ndc<<1;dr=st+1;
  if(st<=dim){val=p[heap[st]];if(val<min){nd=st;min=val;}}
  if(dr<=dim){val=p[heap[dr]];if(val<min){nd=dr;min=val;}}
  if(nd!=ndc)
  {
    sph[heap[ndc]]^=sph[heap[nd]]^=sph[heap[ndc]]^=sph[heap[nd]];
    heap[ndc]^=heap[nd]^=heap[ndc]^=heap[nd];
    rec(nd,dim);
  }
}
int main()
{
  int dh,i,a,b,c,s,t,nn,nd;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=n;i++)
  {
    vec[i]=NULL;
    p[i]=inf;
    u[i]=0;
    sph[i]=i;
    heap[i]=i;
  }
  p[1]=0;
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d%d",&a,&b,&c);
    q=new nod;
    q->sp=b;
    q->cost=c;
    q->urm=vec[a];
    vec[a]=q;
  }
  dh=n;
  fclose(fin);
  for(i=1;i<n;i++)
  {
    nd=heap[1];
    u[nd]=1;
    heap[1]^=heap[dh]^=heap[1]^=heap[dh];
    dh--;
    sph[heap[1]]=1;
    rec(1,dh);
    q=vec[nd];
    while(q)
    {
      nn=q->sp;
      c=q->cost;
      if(!u[nn]&&p[nd]+c<p[nn])
      {
	p[nn]=p[nd]+c;
	s=sph[nn];
	t=s>>1;
	while(t&&p[nn]<p[heap[t]])
	{
	  sph[nn]^=sph[heap[t]]^=sph[nn]^=sph[heap[t]];
	  heap[s]^=heap[t]^=heap[s]^=heap[t];
	  s=t;
	  t=s>>1;
	}
      }
      q=q->urm;
    }
  }
  for(i=2;i<=n;i++)
    if(p[i]==inf) fprintf(fout,"0 ");
    else fprintf(fout,"%d%c",p[i],' ');
  fclose(fout);
  return 0;
}