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

using namespace std;

const int nmax = 50000;

int h[nmax + 1], u[nmax + 1], c[nmax + 1];
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) {
    int f = p / 2;
    while (c[h[p]] < c[h[f]]) {
        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[r] < c[l]) {
            best = r;
        }

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

        p = best;
    }

}

void heap_insert(int x) {
    ++h_size;
    h[h_size] = x;
    u[x] = h_size;

    heap_up(h_size);
}

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

    while (h_size > 0) {
        x = h[1];
        heap_erase(x);

        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;
    edge aux;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        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) {
        printf("%d ", c[i]);
    }

    return 0;
}