#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define MOD 666013

const int NMAX = 5e4;

vector <pair<int, int>> g[NMAX + 5];
priority_queue<pair<int, int>, vector<pair<int, int >>, greater<pair<int, int>>> pq;
int dist[NMAX + 5];
bool viz[NMAX + 5];

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    ios::sync_with_stdio(false), fin.tie(0);
    int n, m;
    fin >> n >> m;
    for (int i = 1, a, b, c; i <= m; i++) {
        fin >> a >> b >> c;
        g[a].pb({b, c});
    }

    for (int i = 2; i <= n; i++) dist[i] = INT_MAX;
    dist[1] = 0;

    pq.push({dist[1], 1});
    while (!pq.empty()) {
        auto u = pq.top();
        pq.pop();
        if (viz[u.second]) continue;
        viz[u.second] = true;
        for (auto x: g[u.second]) {
            dist[x.first] = min(dist[x.first], dist[u.second] + x.second);
            pq.push({dist[x.second], x.first});
        }
    }

    for (int i = 2; i <= n; i++) fout << dist[i] << " ";
    return 0;
}