#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

const int nmax = 50000;

int h[nmax + 1], u[nmax + 1], c[nmax + 1];
//in h[x] tin minte unde se afla nodul x in heap, in u[x] tin minte unde se gaseste nodul x, in c[x] tin minte costul nodului x

int h_size;
bool viz[nmax + 1];

struct edge{
    int y, p;
};
vector <edge> g[nmax + 1];

void heap_swap(int a, int b){
    swap(u[h[a]], u[h[b]]);
    swap(h[a], h[b]);
}

void heap_up(int p) { // percolare
    int f = p / 2;
    while (c[h[p]] < c[h[f]]) { // atata timp cat este mai ieftin decat tatal
        heap_swap(p, f);
        p = p / 2;
        f = p / 2;
    }
}

void heap_down(int p) {
    int best, l, r;
    while (2 * p <= h_size) {
        l = 2 * p;
        best = l;

        r = 2 * p + 1;
        if (r <= h_size && c[h[r]] < c[h[l]]) {
            best = r;
        }

        if (c[h[p]] > c[h[best]]) {
            heap_swap(p, best);
        } else {
            break;
        }

        p = best;
    }

}

void heap_insert(int x) {
    ++h_size;
    //crestem dimensiunea heapului

    h[h_size] = x;
    //pe ultima pozitie se va afla valoarea x

    u[x] = h_size;
    //unde il gasim pe x? pe pozitia h_size

    heap_up(h_size);
    //percolate
}

void heap_erase(int x) {
    int p = u[x];

    heap_swap(p, h_size);
    --h_size;

    heap_up(p);
    heap_down(p);
}

void heap_update(int x) {
    int p = u[x];

    heap_up(p);
}

void dijkstra() {
    int x, y, p;

    viz[1] = 1;
    c[1] = 0;
    heap_insert(1);
    //intai introducem radacina in heap (nu in graf)

    while (h_size > 0) {
        x = h[1]; // iau cel mai apropiat nod
        heap_erase(x); // dupa care il scot din heap

        for (int i = 0; i < g[x].size(); ++i) {
            y = g[x][i].y;
            p = g[x][i].p;

            if (viz[y] == 0) {
                viz[y] = 1;
                c[y] = c[x] + p;
                heap_insert(y);
            } else if (c[x] + p < c[y]) {
                c[y] = c[x] + p;
                heap_update(y);
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m, x, y, z;
    //noduri, muchii, A, B, C
    edge aux;
    //pentru a adauga muchii in graf(nu in heap)

    cin >> n >> m;
    //scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> z;
        //scanf("%d%d%d", &x, &y, &z);
        aux.p = z;
        aux.y = y;
        g[x].push_back(aux);
    }

    dijkstra();

    for (int i = 2; i <= n; ++i) {
        cout << c[i] << " ";
    }

    return 0;
}