#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;

struct Graph
{
    int n;
    vector<vector<pair<int, int>>> adj;
    Graph(int n) : n(n), adj(n) {}

    void AddEdge(int a, int b, int c)
    {
        adj[a].emplace_back(b, c);
    }

    vector<int> Dijkstra(int src)
    {
        vector<int> dist(n, 0);
        vector<bool> vis(n, false);
        priority_queue<pair<int, int>> pq;
        pq.emplace(0, src);
        while (!pq.empty())
        {
            int at, node;
            tie(at, node) = pq.top();
            pq.pop();
            at = -at;

            if (vis[node])
                continue;
            vis[node] = true;
            // -----^

            dist[node] = at;
            for (auto itr : adj[node])
            {
                int nei, cost;
                tie(nei, cost) = itr;
                pq.emplace(-(at + cost), nei);
            }
        }
        return dist;
    }
};

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

    int n, m;
    cin >> n >> m;
    Graph graph(n);
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        graph.AddEdge(a, b, c);
    }
    vector<int> dist = graph.Dijkstra(0);
    for (int i = 1; i < n; ++i)
        cout << dist[i] << " ";
    cout << endl;
    return 0;
}