#include<cstdio>
#include<vector>
 
#define NMAX 50100
#define oo 1<<30
 
using namespace std;
 
int N,M,Nheap;
 
int H[NMAX],Hp[NMAX];
int D[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[H[right_son(nod)]]<D[H[son]])
                son=right_son(nod);
            if(D[H[nod]]<D[H[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]) {
                H[++Nheap]=vecin;
                Hp[vecin]=Nheap;
                D[vecin]=D[nod]+G[nod][i].cost;
                percolate(Hp[vecin]);
            }
            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++)
        if(D[i]==oo)
            printf("0 ");
        else
            printf("%d ",D[i]);
}
 
int main(){
 
    Read();
    Dijkstra();
    Print();
    return 0;
}