#include <cstdio>
#include <vector>
 
#define NMAX 50100
#define vecin first
#define cost second
 
using namespace std;
 
int N,M,Nheap;
 
int H[NMAX];
int P[NMAX];
int D[NMAX];
// int A[NMAX];
 
vector < pair < int , int > > 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;
}
 
inline bool cmp(int i, int j) {
 
    return( D[H[i]] < D[H[j]] );
}
 
void percolate(int nod) {
 
    while(nod>1 && cmp(nod,father(nod))) {
        swap(H[nod],H[father(nod)]);
        swap(P[H[nod]],P[H[father(nod)]]);
        nod=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 && cmp(right_son(nod),son))
                son=right_son(nod);
            if(cmp(nod,son))
                son=0;
        }
 
        if(son) {
            swap(H[nod],H[son]);
            swap(P[H[nod]],P[H[son]]);
            nod=son;
        }
    }while(son);
}
 
void Read() {
 
    freopen("dijkstra.in","r",stdin);
    int x,y,cost;
    scanf("%d%d",&N,&M);
    while(M--) {
        scanf("%d%d%d",&x,&y,&cost);
        G[x].push_back(make_pair(y,cost));
    }
}
 
void Dijkstra() {
 
    int svec,nod;
    Nheap=1;
    H[1]=1;
    P[1]=1;
 
    while(Nheap) {
 
        nod=H[1];
        P[nod]=-1;
        H[1]=H[Nheap--];
        P[H[1]]=1;
        sift(1);
 
        for(unsigned i=0;i<G[nod].size();++i) {
            svec=G[nod][i].vecin;
            if(!P[svec]) {
                H[++Nheap]=svec;
                P[svec]=Nheap;
                D[svec]=D[nod]+G[nod][i].cost;
                // A[svec]=nod;
                percolate(Nheap);
            }
            else {
                if(D[svec]>D[nod]+G[nod][i].cost) {
                    D[svec]=D[nod]+G[nod][i].cost;
                    // A[svec]=nod;
                    percolate(P[svec]);
                }
            }
        }
    }
}
 
void Print() {
 
    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=N;i++)
        printf("%d ",D[i]);
    printf("\n");
}
 
int main() {
 
    Read();
    Dijkstra();
    Print();
    return 0;
}