#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector < int > d;
vector < bool > state;
vector < pair < int, int > > v[50002];
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > q;

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m; f >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c; f >> a >> b >> c;
        v[a].push_back({b, c});
    }

    for(int i = 0; i <= n; i++) {
        state.push_back(0);
        d.push_back(INT32_MAX);
    }
    d[1] = 0;
    q.push({0, 1});
    while(!q.empty()) {
        auto x = q.top();
        state[x.second] = 0;
        q.pop();
        for(int i = 0; i < v[x.second].size(); i++)
            if(d[x.second] + v[x.second][i].second < d[v[x.second][i].first]) {
                d[v[x.second][i].first] = d[x.second] + v[x.second][i].second;
                if(state[v[x.second][i].first] == 0) {
                    q.push({d[v[x.second][i].second], v[x.second][i].first});
                    state[v[x.second][i].first] = 1;
                }
            }
    }
    for(int i = 2; i <= n; i++) {
        if(d[i] == INT32_MAX)
            g << "0\n";
        else
            g << d[i] << ' ';
    }
    g << '\n';
    f.close();
    g.close();
    return 0;
}