#include <bits/stdc++.h>

using namespace std;

struct gngtstuff
{
    pair<int, int> heap[250005];
    int siz = 0;
    pair<int, int> get_max()
    {
        return heap[1];
    }
    int stanga(int ind)
    {
        return ind << 1;
    }
    int dreapta(int ind)
    {
        return (ind << 1) + 1;
    }
    int daddy(int ind)
    {
        return ind >> 1;
    }
    void add(int val, int indice)
    {
        heap[++siz] = {val, indice};
        int nod = siz;
        while (nod != 1)
        {
            int tmp = daddy(nod);
            if (heap[nod] > heap[tmp])
            {
                swap(heap[nod], heap[tmp]);
                nod = tmp;
            }
            else break;
        }
    }
    void pop()
    {
        swap(heap[1], heap[siz]);
        siz--;
        int nod = 1;
        while (nod <= siz)
        {
            int tmp1 = stanga(nod), tmp2 = dreapta(nod);
            if (tmp1 > siz) break;
            else if (tmp2 > siz) tmp2 = tmp1;
            if (heap[tmp1] < heap[tmp2]) swap(tmp1, tmp2);
            if (heap[tmp1] > heap[nod]) {
                swap(heap[tmp1], heap[nod]);
                nod = tmp1;
            }
            else break;
        }
    }
};

gngtstuff sybau;
int ans[100005];
vector<pair<int, int>> edges[100005];

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int x, y, e;
        cin >> x >> y >> e;
        edges[x].push_back({y, e});
    }
    for (i = 2; i <= n; i++) ans[i] = 1e9;
    sybau.add(0, 1);
    while (sybau.siz != 0)
    {
        int a = sybau.heap[1].second, b = -sybau.heap[1].first;
        //cerr << b << '\n';
        sybau.pop();
        if (b > ans[a]) continue;
        for (i = 0; i < edges[a].size(); i++)
        {
            int where = edges[a][i].first, how = b + edges[a][i].second;
            if (how < ans[where])
            {
                ans[where] = how;
                sybau.add(-how, where);
            }
        }
    }
    for (i = 2; i <= n; i++) cout << ((ans[i] != 1e9) ? ans[i] : 0) << ' ';
    return 0;
}
/*
8 7
6 5 1
1 3 2
4 5 3
1 5 8
3 5 3
4 6 1
1 4 1


*/