#include <bits/stdc++.h>
using namespace std;
int d[50001];
vector<vector<pair<int,int>>>adj(200001);
struct cmp{
    bool operator()(int a, int b){
        return d[a] > d[b];
    }
};
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m;
    cin >> n >> m;
    
    priority_queue<int,vector<int>,cmp>q;
    for(int i = 0;i<n;i++){
        d[i] = 1e9;
    }
    for(int i = 0;i<m;i++){
        int a,b,w;
        cin >> a >> b >> w;
        a--;
        b--;
        adj[a].push_back({b,w});
    }
    d[0] = 0;
    q.push(0);
    while(q.size()){
        int nod = q.top();
        q.pop();
        for(auto v : adj[nod]){
            int vecin = v.first;
            int weight = v.second;
            if(d[nod] + weight < d[vecin]){
                d[vecin] = d[nod] + weight;
                q.push(vecin);
            }
        }
    }
    for(int i = 1; i<n;i++) cout << d[i]<<" ";
    
    

    return 0;
}