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

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

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

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

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

void add_edge(const int u, const int v, const int cost)
{
    G[u].push_back({cost, v});
    return;
}

void read()
{
    int m = 0;
    f >> n >> m;

    int u = 0, v = 0, x = 0;
    for (int e = 1; e <= m; ++e)
    {
        f >> u >> v >> x;

        add_edge(u, v, x);
    }

    return;
}

auto cmp = [](const PII &x, const PII &y)
{
    if (!(x.first < y.first))
        return 1;
    return 0;
};

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

    priority_queue<PII, vector<PII>, decltype(cmp)> H(cmp);

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

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

        if (H.empty())
            return d;

        int node = H.top().second;
        used[node] = true;

        H.pop();

        int new_cost = 0;

        for (const PII &e : G[node])
            if ((new_cost = (d[node] + e.first)) < d[e.second])
                d[e.second] = new_cost, H.push({new_cost, e.second});
    }

    return d;
}

int main()
{
    read();

    vector<int> dist = Dijkstra(SOURCE);

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

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

    return 0;
}