# include <stdio.h>
int s[50001],d[50001],i,j,n,m,poz,x,y,z,inf=32000000,ok;
struct nod
{
 int info,cost;
 nod *urm;
}*a[50001],*p,*v,*min,*w,*q;


int main ()
{
freopen ("dijkstra.in","r",stdin);
freopen ("dijkstra.out","w",stdout);
scanf ("%i%i",&n,&m);
for (i=1;i<=m;i++)
{
  scanf ("%i%i%i",&x,&y,&z);
  p=new nod;
p->info=y;
p->cost=z;
p->urm=a[x];
a[x]=p;


 if (x==1)
 {
   d[y]=z;
   p=new nod;
   p->info=y;
   p->cost=z;
   p->urm=v;
   v=p;

 }
}
 for (i=1;i<=n;i++)
  if (d[i]==0)
   d[i]=inf;
while (v)
{
 ok=0;
 p=v;
 min=new nod;
 min->info=inf;
 min->cost=inf;
 q=new nod;
 q->info=inf;

 while (p)
{
 if (min->cost>d[p->info])
 if (q->info!=inf)
{
 min=q;
 ok=0;
 min->cost=d[p->info];
}
else
{
 ok=1;
 min=p;
 min->cost=d[p->info];
}
 q=p;
 p=p->urm;

}
 if (ok==0)
 {
  p=a[min->urm->info];
  poz=min->urm->info;
  min->urm=min->urm->urm;
 }
else
{
 p=a[min->info];
 poz=min->info;
 min=min->urm;
 v=v->urm;
}


while (p)
{
 if (d[p->info]>d[poz]+p->cost)
 {
  d[p->info]=d[poz]+p->cost;
  w=p;
  w->urm=v;
  v=w;
 }
 p=p->urm;
 }


}






for (i=2;i<=n;i++)
 if (d[i]!=inf)
 printf ("%i ",d[i]);
 else
 printf ("0 ");
 return 0;
}