#include<cstdio>
#include<vector>

#define NMAX 50015
#define oo 1<<30

using namespace std;

int N,M,Nheap;

int H[NMAX],Hp[NMAX];     // H[]  = heap pe distante
int D[NMAX];       // D[i] = dist (1,i)
bool used[NMAX];

struct nod{
    int vecin,cost;
};

vector < nod > G[NMAX];

inline int father(int nod){
    return nod>>1;
}

inline int left_son(int nod){
    return nod<<1;
}

inline int right_son(int nod){
    return (nod<<1)+1;
}

void percolate(int nod){

    while(nod>1 && D[H[nod]]<D[H[father(nod)]]){
        swap(H[nod],H[father(nod)]);
        swap(Hp[H[nod]],Hp[H[father(nod)]]);
        }
}

void sift(int nod){

    int son;
    do{
        son=0;
        if(left_son(nod)<=Nheap){
            son=left_son(nod);
            if(right_son(nod)<=Nheap && D[right_son(nod)]<D[son])
                son=right_son(nod);
            if(D[nod]<D[son])
                son=0;
            }
        if(son) {
            swap(H[nod],H[son]);
            swap(Hp[H[nod]],Hp[H[son]]);
            nod=son;
        }
    }while(son);
}

void Read(){

    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&N,&M);
    int i,nod1,nod2,cost;
    for(i=1;i<=M;i++){
        scanf("%d%d%d",&nod1,&nod2,&cost);
        G[nod1].push_back({nod2,cost});
        }
}

void Dijkstra() {

    int nod,vecin;
    Nheap=1;
    H[1]=1;
    Hp[1]=1;
    while(Nheap) {
        nod=H[1];
        Hp[nod]=-1;
        H[1]=H[Nheap--];
        Hp[H[1]]=1;
        sift(1);

        for(unsigned i=0;i<G[nod].size();i++) {
            vecin=G[nod][i].vecin;
            if(!Hp[vecin]) {            //initializam distanta pentru nodul vecin
                H[++Nheap]=vecin;
                Hp[vecin]=Nheap;
                D[vecin]=D[nod]+G[nod][i].cost;
                percolate(Nheap);
            }
            else
                if(D[vecin]>D[nod]+G[nod][i].cost){
                    D[vecin]=D[nod]+G[nod][i].cost;
                    percolate(Hp[vecin]);
                }
        }
    }
}

void Print(){

    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=N;i++)
        printf("%d ",D[i]);
}

int main(){

    Read();
    Dijkstra();
    Print();
    return 0;
}