#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)]]);
    }
}

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;
}