#include <bits/stdc++.h>
#define MAXN 50000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int main() {
    int n, m;
    fin >> n >> m;
    vector<vector<pair<int, int>>> graph(n, vector<pair<int, int>>());
    for (int i = 0; i < m; i++) {
        int from, to, dist;
        fin >> from >> to >> dist;
        from--, to--;
        graph[from].emplace_back( to, dist );
    }

    std::set<pair<int, int>, std::less<>> pq;
    pq.insert({0, 0});
    int dist[MAXN];
    for (int i = 0; i < n; i++)
        dist[i] = INT_MAX;

    while (!pq.empty()) {
        int node = pq.begin()->first;
        int currentDist = pq.begin()->second;
        pq.erase(pq.begin());

        for (auto& neighbour: graph[node]) {
            if (currentDist + neighbour.second < dist[neighbour.first]) {
                dist[neighbour.first] = currentDist + neighbour.second;
                pq.insert({ neighbour.first, dist[neighbour.first] });
            }
        }
    }

    for (int i = 1; i < n; i++)
        fout << (dist[i] == INT_MAX ? 0 : dist[i]) << ' ';
    return 0;
}