#include <fstream>
#include <set>
#include <queue>

using namespace::std;

int n, m;
vector<vector<pair<int, int>>> g;
priority_queue<pair<int, int>> pq;

int main() {
    ifstream fin("dijkstra.in");
    fin >> n >> m;

    g.resize(n + 1);
    while(m--) {
        int a, b,c;
        fin >> a >> b >>c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    vector<int> bestDist(n, 1000000000);

    pq.push({0, 1});
    while(pq.size()) {
        pair<int, int> p = pq.top();
        pq.pop();
        int currNode = p.second;
        int currDist = -p.first;

        for(pair<int, int> &edge: g[currNode]) {
            if (currDist + edge.second < bestDist[edge.first]) {
                bestDist[edge.first] = currDist + edge.second;
                pq.push({-bestDist[edge.first], edge.first});
            }
        }
    }

    ofstream fout("dijkstra.out");
    for(int i = 2; i <= n; i++) {
        fout << bestDist[i] << ' ';
    }
}