#include <stdio.h>
#include <stdlib.h>
#define MAXN 50000
#define MAXM 250000
int l[MAXM+1],v[MAXM+1],next[MAXM+1],ind[MAXN+1],lung[MAXN+1],v1[MAXM],con=1,vf[MAXN+1];
typedef int Heap[MAXM];
Heap H;
inline int lson(int nod){
    return 2*nod+1;
}
inline int rson(int nod){
    return 2*nod+2;
}
inline int father(int nod){
    return (nod-1)/2;
}
inline void coborare(int nod,int conh){
    int flag=1;
    while(flag&&lson(nod)<conh){
        if(rson(nod)<conh&&H[rson(nod)]<H[lson(nod)]&&H[nod]>H[rson(nod)]){
            swapH(nod,rson(nod));
            swapv1(nod,rson(nod));
            nod=rson(nod);
        }
        else
            if(H[lson(nod)]>H[nod]){
                swapH(nod,lson(nod));
                swapv1(nod,lson(nod));
                nod=lson(nod);
            }
            else
                flag=0;
    }
}
inline void urcare(int nod){
    int flag=1;
    while(nod>0&&flag){
        if(H[father(nod)]>H[nod]){
            swapH(father(nod),nod);
            swapv1(father(nod),nod);
            nod=father(nod);
        }
        else
            flag=0;
    }
}
inline void add(int x,int y,int z){
    v[con]=y;
    l[con]=z;
    next[con]=ind[x];
    ind[x]=con;
    con++;
}
inline void swapH(int x,int y){
    int aux=H[x];
    H[x]=H[y];
    H[y]=aux;
}
inline void swapv1(int x,int y){
    int aux=v1[x];
    v1[x]=v1[y];
    v1[y]=aux;
}
int main(){
    FILE*fi,*fout;
    int n,m,x,y,z,i,conh,poz,s;
    fi=fopen("dijkstra.in" ,"r");
    fout=fopen("dijkstra.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i=0;i<m;i++){
        fscanf(fi,"%d%d%d" ,&x,&y,&z);
        add(x,y,z);
    }
    poz=ind[1];
    conh=0;
    while(poz){
        H[conh]=l[poz];
        v1[conh]=v[poz];
        vf[v[poz]]=1;
        urcare(conh);
        conh++;
        poz=next[poz];
    }
    i=0;
    while(i<n-1){
        poz=ind[v1[0]];
        s=H[0];
        lung[v1[0]]=H[0];
        conh--;
        swapH(0,conh);
        swapv1(0,conh);
        coborare(0,conh);
        while(poz){
            if(vf[v[poz]]==0){
                vf[v[poz]]=1;
                H[conh]=s+l[poz];
                v1[conh++]=v[poz];
                urcare(conh-1);
            }
            poz=next[poz];
        }
        i++;
    }
    for(i=2;i<=n;i++)
        fprintf(fout,"%d " ,lung[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}