#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>>adj(50000);
int d[50000];
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;
    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});
    }
    
    priority_queue<int,vector<int>,cmp>q;
    
    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 dist = v.second;
            if(d[nod] + dist < d[vecin]){
                d[vecin] = dist + d[nod];
                q.push(vecin);
            }
        }
        
    }
    
    for(int i = 1;i<n;i++){
        cout << d[i]<<" ";
    }
    

    return 0;
}