#include <fstream>
#include <vector>

using namespace std;

const int INF = 1e9 + 1;

struct muchie {
    int x, y, c;
    int celalalt(int vf) {
        return (x + y - vf);
    }
};

vector <int> h, d, poz_in_h;

void schimb(int p1, int p2) {
    swap(h[p1], h[p2]);
    poz_in_h[h[p1]] = p1;
    poz_in_h[h[p2]] = p2;
}

void adauga(int x) {
    h.push_back(x);
    poz_in_h[x] = (int)h.size() - 1;
}

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

int fiu_stang(int p) {
    return 2 * p + 1;
}

int fiu_drept(int p) {
    return 2 * p + 2;
}

void coboara(int p) {
    int fs = fiu_stang(p), fd = fiu_drept(p), p_min = p;
    if (fs < h.size() && d[h[fs]] < d[h[p_min]]) {
        p_min = fs;
    }
    if (fd < h.size() && d[h[fd]] < d[h[p_min]]) {
        p_min = fd;
    }
    if (p_min != p) {
        schimb(p_min, p);
        coboara(p_min);
    }
}

void sterge() {
    schimb(0, (int)h.size() - 1);
    h.pop_back();
    coboara(0);
}

void urca(int p) {
    while (p > 0 && d[h[p]] < d[h[tata(p)]]) {
        schimb(p, tata(p));
        p = tata(p);
    }
}

int main() {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m;
    in >> n >> m;
    vector <muchie> e(m);
    vector <vector <int>> lst_a(n + 1);
    for (int i = 0; i < m; i++) {
        in >> e[i].x >> e[i].y >> e[i].c;
        lst_a[e[i].x].push_back(i);
        lst_a[e[i].y].push_back(i);
    }
    in.close();
    d.resize(n + 1, INF);
    poz_in_h.resize(n + 1, -1);
    d[1] = 0;
    for (int i = 1; i <= n; i++) {
        adauga(i);
    }
    while (!h.empty()) {
        int x = h.front();
        sterge();
        for (auto i: lst_a[x]) {
            int y = e[i].celalalt(x);
            if (d[x] + e[i].c < d[y]) {
                d[y] = d[x] + e[i].c;
                urca(poz_in_h[y]);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (d[i] == INF) {
            d[i] = 0;
        }
        out << d[i] << " ";
    }
    out << "\n";
    out.close();
    return 0;
}