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

constexpr int inf = 1e9 + 100, maxn = 5e4 + 100;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int, int>> vec[maxn] = {};
bitset<maxn> viz = 0;
priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>>
    pq;
int dist[maxn] = {}, n, m;

void djk(){
    fill(dist, dist+maxn, inf);
    dist[0] = 0;
    pq.emplace(0, 0);
    for(int cur, cur_dist; !pq.empty(); ){
        tie(cur_dist, cur) = pq.top();
        pq.pop();
        if(dist[cur] != cur_dist) continue;
        for(const auto next : vec[cur]){
            if(dist[next.second] <= cur_dist + next.first) continue;
            dist[next.second]     = cur_dist + next.first; 
            pq.emplace(dist[next.second], next.second); } } }

int main(){
    f >> n >> m;
    for(int i = 0, x, y, c; i < m; ++i){
        f >> x >> y >> c;
        --x, --y;
        vec[x].emplace_back(c, y); }
    djk();
    replace(dist, dist+maxn, inf, 0);
    for(int i = 1; i < n; ++i) g << dist[i] << ' ';
    return 0; }