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

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

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

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

int d[nMAX];
bool vizited[nMAX];

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

static inline void add_edge(const int x, const int y, const int c)
{
    G[x].push_back({c, y});
    return;
}

static inline void read()
{
    ifstream f("dijkstra.in");
    f.tie(nullptr);

    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, add_edge(u, v, c);

    return;
}

static inline void init()
{
    for (int i = 1; i <= n; ++i)
        d[i] = INF, vizited[i] = false;

    return;
}

static inline void dijkstra(const int S)
{
    init();

    d[S] = 0, vizited[S] = true;
    for (const edge &e : G[S])
        if (e.first < d[e.second])
            d[e.second] = e.first, H.push(e);

    int min_node = 0;

    while (!H.empty())
    {
        while ((!H.empty()) && (vizited[H.top().second] == true))
            H.pop();

        if (H.empty())
            break;

        min_node = H.top().second;
        vizited[min_node] = true;
        H.pop();

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

    return;
}

int main()
{
    read();

    dijkstra(1);

    ofstream g("dijkstra.out");
    g.tie(nullptr);

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

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

    return 0;
}