#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;


int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int N, M;
    cin >> N >> M;

    vector<vector<pi>> adj(N + 1);
    while (M--)
    {
        int x, y, weight;
        cin >> x >> y >> weight;

        adj[x].emplace_back(y, weight);
    }

    vector<int> shortest_dist(N + 1, 2e9);
    auto Dijkstra = [&](const int start_node) -> void
    {
        priority_queue<pi, vector<pi>, greater<pi>> nodes;
        nodes.emplace(0, start_node);
        shortest_dist[start_node] = 0;

        while (!nodes.empty())
        {
            const int cur_node = nodes.top().second, dist_from_start_node = nodes.top().first;
            nodes.pop();

            if (dist_from_start_node != shortest_dist[cur_node])
            {
                continue;
            }

            for (const auto &_adj_node : adj[cur_node])
            {
                const int adj_node = _adj_node.first, weight = _adj_node.second;

                if (dist_from_start_node + weight < shortest_dist[adj_node])
                {
                    nodes.emplace(shortest_dist[adj_node] = dist_from_start_node + weight, adj_node);
                }
            }
        }
    };

    Dijkstra(1);

    for (int node = 2; node <= N; ++node)
    {
        cout << (shortest_dist[node] == 2e9 ? 0 : shortest_dist[node]) << " ";
    }
}