#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
// #define LOCAL
#ifdef LOCAL
ifstream cin("input.txt");
ofstream cout("output2.txt");
#else
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#endif
#define cin ::cin
#define cout ::cout


int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<pi>> adj;
    adj.resize(N + 1);
    while (M--)
    {
        int A, B, C;
        cin >> A >> B >> C;
        adj[A].push_back({B, C});
    }

    const int source_vertex = 1;
    const int INF = 2e9;

    [&]() -> void
    {
        vector<int> shortest_paths(N + 1, INF);
        priority_queue<pi, vector<pi>, greater<pi>> unmarked_nodes;  // MIN-HEAP
        unmarked_nodes.push({0, source_vertex});
        shortest_paths[source_vertex] = 0;
        while (!unmarked_nodes.empty())
        {
            const int min_node = unmarked_nodes.top().second;
            const int cur_dist_from_start_node = unmarked_nodes.top().first;
            unmarked_nodes.pop();
            if (shortest_paths[min_node] == INF)
            {
                break;
            }
            if (cur_dist_from_start_node != shortest_paths[min_node])
            {
                continue;
            }

            for (const auto &anode : adj[min_node])
            {
                const int adj_node = anode.first;
                const int weight = anode.second;
                if (shortest_paths[min_node] + weight < shortest_paths[adj_node])
                {
                    shortest_paths[adj_node] = shortest_paths[min_node] + weight;  // RELAX BRO
                    unmarked_nodes.push({shortest_paths[adj_node], adj_node});
                }
            }
        }

        for (int i = 2; i <= N; ++i)
        {
            cout << (shortest_paths[i] == INF ? 0 : shortest_paths[i]) << " ";
        }
    }();
}