#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define INF INT_MAX
void dijkstra(int start,vector<int> &dist, int n, vector<vector<pair<int,int>>> &adj){
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist.assign(n+1, INT_MAX);
    dist[start] = 0;
    pq.push({0, start});
    while(!pq.empty()){
        pair<int,int> top = pq.top();
        pq.pop();
        int d = top.first;
        int u = top.second;

        if(d > dist[u]) continue;

        for(pair<int,int> vecin : adj[u]){
            int v = vecin.first;
            int w = vecin.second;
            if(dist[v] > d + w){
                dist[v] = d+w;
                pq.push({w,v});
            } 
        }
        
    }
}

int main(){
    int n,m;
    fin >> n >> m;
    vector<int> dist(n+1);
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 1; i<=m; i++){
        int a,b,c;
        fin >> a >> b >> c;
        adj[a].push_back({b,c});
    }
    dijkstra(1, dist, n, adj);
    for(int i = 2; i<=n; i++){
        fout << dist[i] << ' ';
    }


    return 0;
}