#include <fstream>
#include <vector>
#include <queue>

using namespace std;
using edge = pair<int, int>;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

static constexpr int nMAX = ((int)(5e4) + 1), INF = ((int)(1e9));

int n = 0;
vector<edge> G[nMAX];

auto cmp_min = [](const edge &x, const edge &y)
{
    if (!(x.first < y.first))
        return 1;
    return 0;
};
using min_heap = priority_queue<edge, vector<edge>, decltype(cmp_min)>;

void load_graph()
{
    f >> n;

    int m = 0;
    f >> m;

    int u = 0, v = 0, c = 0;

    for (int i = 1; i <= m; ++i)
    {
        f >> u >> v >> c;
        G[u].push_back({c, v});
    }

    return;
}

int main()
{
    load_graph();

    vector<int> d((n + 1), INF);
    vector<bool> used((n + 1), false);

    min_heap H(cmp_min);

    d[1] = 0, used[1] = true;

    for (const edge &it : G[1])
        if (it.first < d[it.second])
            d[it.second] = it.first, H.push(it);

    while (!H.empty())
    {
        while ((!H.empty()) && (used[H.top().second]))
            H.pop();

        if (H.empty())
            break;

        int node = H.top().second;

        used[node] = true;
        H.pop();

        for (const edge &it : G[node])
            if (!used[it.second])
                if ((d[node] + it.first) < d[it.second])
                    d[it.second] = (d[node] + it.first),
                    H.push({d[it.second], it.second});
    }

    for (int i = 2; i <= n; ++i)
    {
        g << ((d[i] == INF) ? 0 : d[i]);

        if (i != n)
            g << ' ';
        else
            g << '\n';
    }

    return 0;
}