#include <bits/stdc++.h>
#define int long long

using namespace std;

const int NMAX = 50005;

priority_queue<pair<int, int>> pq;
vector<pair<int, int>> adj[NMAX];
int save[NMAX];

signed main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n, m, a, b, val;
    cin>>n>>m;

    for(int i=1; i<=n; i++)
        save[i] = 21e8;

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

    pq.push({0, 1});
    save[1] = 0;

    while(pq.empty() == false)
    {
        int nod = pq.top().second, cur_cost = -pq.top().first; pq.pop();

        if(cur_cost != save[nod])
            continue;

        for(auto x : adj[nod])
        {
            int new_nod = x.first, to_cost = x.second;
            if(save[new_nod] > save[nod] + to_cost)
            {
                save[new_nod] = save[nod] + to_cost;
                pq.push({-save[new_nod], new_nod});
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        if(save[i] == 21e8) cout<<0<<" ";
        else cout<<save[i]<<" ";
    }

    return 0;
}