#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int n,m;
ll d[100000];
bool vis[100000];
vector<vector<pair<int,ll>>>adj(100000);

struct cmp{
    bool operator()(int a, int b){
        return(a > b);
    }
};

int main()
{
    freopen("dijkstra.in","r",stdin);
     freopen("dijkstra.out","w",stdout);
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        d[i] = (1<<30);
    }
    for(int i = 0;i<m;i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--;
        b--;
        adj[a].pb({b,c});
    }
    
    priority_queue<int,vector<int>,cmp>pq;
    d[0] = 0;
    pq.push(0);
    vis[0] = 1;
    
    while(pq.size()){
        int nod = pq.top();
        pq.pop();
        vis[nod] = 0;
        for(auto vc : adj[nod]){
            int v = vc.first;
            ll dist = vc.second;
            
                if(d[v] > d[nod] + dist){
                    
                    d[v] = d[nod] + dist;
                    
                    if(!vis[v]){
                        vis[v] = 1;
                        pq.push(v);
                    }
                    
                }
            
        }
    }
    for(int i = 0;i<n;i++) cout<<d[i]<<" ";
    
    
    
    
    

    return 0;
}