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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX=5e4+1;

vector<pair<int, int>> adj[NMAX];
int n, m, dist[NMAX];
bool processed[NMAX];

int main(){
    fin >> n >> m;
    while(m--){
        int x, y, w;
        fin >> x >> y >> w;
        adj[x].push_back({y, w});
    }
    for(int i=2; i<=n; i++) dist[i]=INT_MAX/2;
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    while(!q.empty()){
        int s=q.top().second; q.pop();
        if(processed[s]) continue;
        processed[s]=true;
        for(auto u : adj[s]){
            if(dist[u.first]>dist[s]+u.second){
                dist[u.first]=dist[s]+u.second;
                q.push({-dist[u.first], u.first});
            }
        }
    }
    for(int i=2; i<=n; i++){
        fout << dist[i] << ' ';
    }
}