#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;

const int Nmx = 50100;

vector<pair<int,int>> adj[Nmx];
int N, M, a, b, w;
int dist[Nmx];
bool vis[Nmx];
priority_queue<pair<int,int>> q;
int main(){
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> a >> b >> w;
        adj[a].push_back({b,w});
    }

    for(int i = 2; i <= N; i++) dist[i] = INF;
    q.push({0,1});

    while(!q.empty()){
        a = q.top().second; q.pop();
        if(vis[a]) continue;
        vis[a] = true;
        for(auto u: adj[a]){
            b = u.first; w = u.second; 
            if(dist[a] + w < dist[b]){
                dist[b] = dist[a]+w;
                q.push({-dist[b],b});
            }
        }
    }

    for(int i = 2; i <= N; i++) cout << dist[i] << " ";


}