/// Solutie in O(M log N)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int MAX_N = 5e4 + 5;
const int SOURCE_NODE = 1;
const int INF = 1e9;

vector<pair<int, int>> G[MAX_N];
int n, m, x, y, cost;

void Init()
{
    f >> n >> m;
    while (m--)
    {
        f >> x >> y >> cost;
        G[x].push_back({cost, y});
    }
}

/// retinem arcele in priority_queue in ordinea crescatoare a costurilor
auto cmp = [](const pair<int, int> &x, const pair<int, int> &y) {
    return x.first > y.first;
};

vector<int> Dijkstra(const int source_node)
{
    vector<int> d(n + 1, INF);
    vector<bool> viz(n + 1, 0);
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> H(cmp);

    d[source_node] = 0;
    viz[source_node] = 1;

    for (const pair<int, int> & edge : G[source_node])
    {
        d[edge.second] = edge.first;
        H.push(edge);
    }

    while (!H.empty())
    {
        while (!H.empty() && viz[H.top().second])
            H.pop();
        if (H.empty())
            return d;

        int node = H.top().second;
        viz[node] = 1;
        H.pop();

        int new_cost = 0;
        for (const pair<int, int> & edge : G[node])
            if ((new_cost = (d[node] + edge.first)) < d[edge.second])
            {
                d[edge.second] = new_cost;
                H.push({new_cost, edge.second});
            }
    }

    return d;
}

int main()
{
    Init();

    vector<int> dist = Dijkstra(SOURCE_NODE);
    for (int i = 2; i <= n; i++)
        g << (dist[i] == INF ? 0 : dist[i]) << ' ';
    g << '\n';

    f.close();
    g.close();
    return 0;
}