#include <stdio.h>
#define inf 1<<30
#define maxn 50005
struct NOD 
       { int info,cost;
         NOD *urm;};
int x,n,m,i,j,min;
int H[maxn];
int D[maxn];
int poz[maxn];
NOD *list[maxn];
NOD *urm;

void shift(int x,int n)
{
     int tata,v,fiu;
     tata = x; fiu=x<<1; v=H[x];
     
     while (fiu<=n)
     {
           if (fiu<n)
            if (D[H[fiu]]>D[H[fiu+1]]) fiu++;
             if (D[v]>D[H[fiu]])
             {
                     H[tata] = H[fiu];
                     poz[H[tata]] = tata;
                     tata = fiu;
                     fiu = tata << 1;
             }
             else fiu = n+1;
             }
     H[tata] = v;
     poz[v] = tata;
}
     
void up(int i,int n)
{
 int tata,fiu,aux;
 fiu = i;
 tata = i>>1;
 while (tata!=0 && D[H[tata]]>D[H[fiu]])
 {
 poz[H[tata]] = fiu;
 poz[H[fiu]] = tata;
 aux = H[tata];
 H[tata] = H[fiu];
 H[fiu] = aux;
 fiu = tata;
 tata = fiu >> 1;
 }    
}    

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    
    for (;m;m--)
    {
        urm = new NOD;
        scanf("%d%d%d",&x,&urm->info,&urm->cost);
        urm->urm = list[x];
        list[x] = urm;
    }
    
    for (i=1;i<=n;i++)
    {
        H[i] = i;
        poz[i] = i;
        D[i] = inf;
    }
    
    urm = list[1];
    while (urm!=NULL)
    {
          D[urm->info] = urm->cost;
          urm = urm->urm;
    }
    
    for (i=n>>1;i>0;i--) shift(i,n);
    
    for (i=n;i>0;i--)
    {
       min = H[1];
       H[1]=H[i];
       shift(1,i-1);
       urm = list[min];
       while (urm!=NULL)
       {
             if (D[urm->info]>D[min]+urm->cost)
                {
                 D[urm->info] = D[min]+urm->cost;
                 up(poz[urm->info],i-1);
                }
             urm = urm->urm;
       } 
    }
    for (i=2;i<=n;i++)
    if (D[i]==inf) printf("0 ");
    else printf("%d ",D[i]);
    
}