#include <stdio.h>
#include <utility>
#include <algorithm>
#define nmax 50010

using namespace std;

int n, m, a, b, c, nr;
int d[nmax], pos[nmax], heap[nmax];
vector <pair<int, int>> g[nmax];

void Swap(int &x, int &y)
{
    swap(x, y); swap(pos[x], pos[y]);
}

void heapup(int v)
{
    int k = heap[v];

    while (v > 1 && d[heap[v]] < d[heap[v / 2]]) {
        Swap(heap[v], heap[v / 2]); v = v / 2;
    }

    heap[v] = k;
}

void heapdown(int v)
{
    int w = v * 2;

    while (w <= nr) {

        if (w < nr && d[heap[w]] > d[heap[w + 1]]) w++;

        if (d[heap[v]] <= d[heap[w]]) break; else
            Swap(heap[v], heap[w]);

        v = w; w *= 2;

    }
}

void remove_heap()
{
    Swap(heap[1], heap[nr]); nr--; heapdown(1);
}

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

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++) {

        scanf("%d %d %d", &a, &b, &c);

        g[a].push_back(make_pair(b, c));

    }

    for (int i = 1; i <= n; i++) {
        heap[i] = i; d[i] = 2e9;  pos[i] = i;
    }

    nr = n; d[1] = 0;

    while (nr > 1) {

        int x = heap[1]; remove_heap();

        for (int i = 0; i < (int)g[x].size(); i++)
        if (d[x] + g[x][i].second < d[g[x][i].first]) {
            d[g[x][i].first] = d[x] + g[x][i].second; heapup(pos[g[x][i].first]);
        }

    }

    for (int i = 2; i <= n; i++)
        if (d[i] == 2e9) printf("0 "); else
            printf("%d ", d[i]);

    return 0;
}