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

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

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

void djk(){
    fill(dist, dist+maxn, inf);
    pq.emplace(0, 0);
    while(!pq.empty()){
        int cur, cur_dist;
        cur_dist = pq.top().first, cur = pq.top().second;

        pq.pop();
        if(dist[cur] <= cur_dist) continue;
        dist[cur] = cur_dist;
        for(const auto next : vec[cur])
            pq.emplace(cur_dist + next.first, 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();
    for(int i = 1; i < n; ++i) g << dist[i] << ' ';
    return 0; }