#include <bits/stdc++.h>

std::ifstream in("dijkstra.in");
std::ofstream out("dijkstra.out");

const int N = 5e4 + 1, M = 25e4 + 1;

struct NodeEdge {
    int to, c, next;
} e[M];
int et = 1, lst[N], h[N], ht, d[N], pos[N], n, m;

void add_edge(int u, int v, int c) {
    e[et] = {v, c, lst[u]};
    lst[u] = et;
    ++et;
}

inline bool h_cmp(int p1, int p2) {
    return d[h[p1]] < d[h[p2]];
}

inline int h_parent(int p) {
    return (p - 1) / 2;
}

void h_swap(int p1, int p2) {
    std::swap(h[p1], h[p2]);
    std::swap(pos[h[p1]], pos[h[p2]]);
}

void h_update_up(int p) {
    while (p != 0 && h_cmp(p, h_parent(p))) {
        h_swap(p, h_parent(p));
        p = h_parent(p);
    }
}

void h_update_down(int p) {
    int l = 2 * p + 1, r = l + 1;
    int pmin = p;
    if (l < ht && h_cmp(l, pmin)) {
        pmin = l;
    }
    if (r < ht && h_cmp(r, pmin)) {
        pmin = r;
    }
    if (pmin != p) {
        h_swap(pmin, p);
        h_update_down(pmin);
    }
}

void h_remove(int p) {
    if (p == ht - 1) {
        --ht;
        return;
    }
    h[p] = h[--ht];
    pos[h[p]] = p;
    h_update_up(p);
    h_update_down(p);
}

inline bool h_empty() {
    return ht == 0;
}

int h_pop() {
    int ret = h[0];
    h_remove(0);
    return ret;
}

void dijkstra(int u0) {
    for (int i = 1; i <= n; ++i) {
        d[i] = std::numeric_limits<int>::max();
    }
    d[u0] = 0;
    h[ht] = u0;
    pos[u0] = ht++;
    while (!h_empty()) {
        int u = h_pop();
        for (int p = lst[u]; p != 0; p = e[p].next) {
            int v = e[p].to, c = e[p].c;
            if (d[u] + c < d[v]) {
                d[v] = d[u] + c;
                if (pos[v] == 0) {
                    h[ht] = v;
                    pos[v] = ht++;
                }
                h_update_up(pos[v]);
            }
        }
    }
}

int main() {
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        in >> u >> v >> c;
        add_edge(u, v, c);
    }
    dijkstra(1);
    for (int i = 2; i <= n; ++i) {
        if (d[i] == std::numeric_limits<int>::max()) {
            d[i] = 0;
        }
        out << d[i] << ' ';
    }
}