#include<stdio.h>   
#include<string.h>   
#define maxn 50001   
#define oo 0x3f3f3f3f   
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");   
  
struct lista{ int nod,c;    
            lista *urm;} *G[maxn];   
int t[maxn],h[maxn],poz[maxn],D[maxn];   
int n,m,x,y,cost,i,nn,nod;   
void swap(int i, int j)   
{   
    int aux;   
    aux=h[i]; h[i]=h[j]; h[j]=aux;   
       
    poz[h[i]]=i;   
    poz[h[j]]=j;   
}   

  
void heapdown(int r,int k)   
{   
    int m=r;   
       
    if(2*r <= k)   
        if(D[ h[2*r] ] < D[ h[m] ]) m=2*r;   
    if(2*r+1 <= k)   
        if(D[ h[2*r+1] ] < D[ h[m] ]) m=2*r+1;   
       
    if(m != r) swap(r, m), heapdown(m, k);   
}   
       
  
  
void heapup(int k)   
{   
    if(k<=1) return;   
    int t=k/2;   
    if(D[h[t]]>D[h[k]])   
    {   
        swap(k,t);   
        heapup(t);   
    }   
}   
  
void build(int k)   
{   
    int i;   
    for(i=2;i<=k;i++) heapup(i);   
}   
       
void dijkstra(int s)   
{   
    int i;   
    lista *p;   
    memset(t,0,sizeof(t));   
    memset(D,oo,sizeof(D));   
       
    for(i=1;i<=n;i++)   
    {   
        h[i]=i;   
        poz[i]=i;   
    }   
       
    D[s]=0;   
    build(n);   
    nn=n;   
       
    while(nn>0)   
    {   
        nod=h[1];   
        swap(1,nn);   
        nn--;   
        heapdown(1,nn);   
           
           
        for(p=G[nod]; p!=NULL; p=p->urm)   
        {   
            if(D[p->nod]>D[nod]+p->c)   
            {   
                D[p->nod]=D[nod]+p->c;   
                t[p->nod]=nod;   
                heapup(poz[p->nod]);   
            }   
        }   
    }   
}   
  
int main()   
{   
       
    lista *q;   
    fscanf(f,"%d %d\n",&n,&m);   
    for(i=1;i<=m;i++)   
    {   
        fscanf(f,"%d %d %d\n",&x,&y,&cost);   
           
        q= new lista;   
        q->nod=y;   
        q->c=cost;   
        q->urm=G[x];   
        G[x]=q;   
    }   
       
  
    dijkstra(1);   
       
    for(i=2;i<=n;i++)   
            fprintf(g,"%d ", D[i]==oo ? 0 : D[i]);   
    fprintf(g,"\n");   
           
       
    fclose(f);   
    fclose(g);   
    return 0;   
}