#include <bits/stdc++.h>

using namespace std;

priority_queue<pair<int, int>> pq;
vector<pair<int, int>> adj[250005];
bool save[250005];
int rez[250005];

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

    int n, m, a, b, val;
    cin>>n>>m;

    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>val;
        adj[a].push_back({b, val});
    }

    pq.push({0, 1}); /// <cost pana acolo, nod>

    while(!pq.empty())
    {
        int curr_cost = pq.top().first, curr_nod = pq.top().second;
        save[curr_nod] = 1;
        rez[curr_nod] = curr_cost;
        pq.pop();

        for(auto x : adj[curr_nod])
        {
            int nou_nod = x.first, nou_cost = x.second;
            if(save[nou_nod] == 0)
                pq.push({curr_cost + nou_cost, nou_nod});
        }
    }

    for(int i=2; i<=n; i++)
            cout<<rez[i]<<" ";

    return 0;
}