#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 1e5;
const ll inf = 1e15;

vector<vector<pair<ll, int>>> dx(nmax+5);
priority_queue< pair<ll, int>,
                vector<pair<ll, int>>,
                greater<pair<ll, int>>> pq;
ll dp[nmax+5];
bool viz[nmax+5];

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    
    int n, m; f >> n >> m;
    for(int i=1; i<=m; i++) {
        int x, y, c; f >> x >> y >> c;
        dx[x].emplace_back(c, y);
    }

    for(int i=1; i<=n; i++) dp[i] = inf;
    dp[1] = 0;
    pq.emplace(0, 1);
    while(pq.empty() == false) {
        pair<ll, int> temp = pq.top(); pq.pop();
        ll cost = temp.first;
        int node = temp.second;

        if(viz[node]) continue;
        viz[node] = true;
        for(auto i : dx[node])
            if(cost + i.first < dp[i.second]) {
                dp[i.second] = cost + i.first;
                pq.emplace(cost + i.first, i.second);
            }
    }
    for(int i=2; i<=n; i++) g << dp[i] << " ";
    return 0;
}