#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 50002;
const int INF = 0x3f3f3f3f;

typedef int Heap[MAX_N];

int N, M, Nr;
int D[MAX_N], pos[MAX_N];
vector < pair < int, int > > v[MAX_N];
bool m[MAX_N];
Heap H;

inline int father(int k) {
    return k/2;
}

inline int left_son(int k) {
    return 2*k;
}

inline int right_son(int k) {
    return 2*k+1;
}

inline void percolate(Heap H, int N, int K) {
    int temp = H[K];
    while(K > 1 && D[temp] < D[H[father(K)]]) {
        H[K] = H[father(K)], pos[H[K]] = K;
        K = father(K);
    }
    H[K] = temp, pos[temp] = K;
}

inline void sift(Heap H, int N, int K) {
    int son;
    do {
        son = 0;
        if(left_son(K) <= N) {
            son = left_son(K);
            if(right_son(K) <= N && D[H[right_son(K)]] < D[H[son]])
                son = right_son(K);
        }
        if(D[H[son]] >= D[H[K]])
            son = 0;
        if(son) {
            int temp = H[K];
            H[K] = H[son], H[son] = temp;
            pos[H[K]] = K, pos[H[son]] = son;
        }
    } while(son);
}

inline void cut(Heap H, int &N, int K) {
    H[K] = H[N--];
    if(K == N+1)
        return;
    pos[H[K]] = K;
    if(K > 1 && D[H[K]] < D[H[father(K)]])
        percolate(H, N, K);
    else sift(H, N, K);
}

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    f >> N >> M;
    for(int i = 1, x, y, c; i <= M; ++i) {
        f >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }

    for(int i = 2; i <= N; ++i)
        D[i] = INF, H[++Nr] = i, pos[i] = Nr;
    H[++Nr] = 1, pos[1] = Nr;
    percolate(H, Nr, Nr);
    while(Nr) {
        int x = H[1];
        cut(H, Nr, 1);
        m[x] = 1;
        for(size_t i = 0; i < v[x].size(); ++i) {
            int y = v[x][i].first, c = v[x][i].second;
            if(m[y])
                continue;
            if(D[x] + c < D[y]) {
                D[y] = D[x] + c;
                cut(H, Nr, pos[y]);
                H[++Nr] = y, pos[y] = Nr;
                percolate(H, Nr, Nr);
            }
        }
    }

    for(int i = 2; i <= N; ++i) {
        if(D[i] == INF)
            D[i] = 0;
        g << D[i] << ' ';
    }
    g << '\n';

    f.close();
    g.close();

    return 0;
}