#include<stdio.h>
#define dim 50500

#define mod dim
int a[dim],n,m;
struct nod
{
       int x,c;
       nod *next;
} *liste[dim];
int coada[dim],cost[dim];

void add(int  x,int y,int c)
{
     nod *p=new nod;
     p->x=y;
     p->next=liste[x];
     p->c=c;
     liste[x]=p;
}
void read()
{
     int x,y,c;
     scanf("%d%d",&n,&m);
     for(int i=1;i<=m;i++)
     {
             scanf("%d%d%d",&x,&y,&c);
             add(x,y,c);
             }
}
void solve()
{
     int st,dr;
     st=1,dr=1;
     coada[1]=1;
     for(st=1;st!=dr;st++ ,st%=dim)
     {
                          for(nod *p=liste[coada[st]] ; p ; p=p->next)
                          {
                                  if(p->x==1)
                                  continue;
                                                 if(cost[p->x]==0)
                                                 {
                                                                  cost[p->x]=cost[coada[st]] + p->c;
                                                                  dr++;
                                                                  dr%=mod;
                                                                  coada[dr]=p->x;
                                                                  a[p->x]=coada[st];
                                                                  }
                                                 else
                                                 if(cost[p->x]>cost[coada[st]]+p->c)
                                                 {
                                                 cost[p->x]=cost[coada[st]]+p->c; 
                                                 dr++;
                                                 coada[dr]=p->x;
                                                 a[p->x]=coada[st];                         }
                                                 }
                  }
     for(int i=2;i<=n;i++)
     printf("%d ",cost[i]);
}
int main ()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read();
    solve();
    return 0;
}