#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <climits>
#include <queue>
#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector<vector<vector<int>>> adjacent_list(50001);
vector<bool> visited(50001, false);
vector<long long int> min_distance(50001, LONG_MAX);
priority_queue<vector<long long int>> min_heap;


int main() {
    int n, m;
    f >> n >> m;

    min_heap.push({0, 1}); // the first element is the distance, the second one is the node
    min_distance[1] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y, distance;
        f >> x >> y >> distance;
        adjacent_list[x].push_back({distance, y});
    }
    while (!min_heap.empty()) {
        vector<long long int> current_node_info = min_heap.top();
        min_heap.pop();
        int node = current_node_info[1];
        if (visited[node] == false) {
            visited[node] = true;
            for (auto neighbor: adjacent_list[node]) {
                long long int current_distance = min_distance[node] + neighbor[0];
                if (current_distance < min_distance[neighbor[1]] && visited[neighbor[1]] == false) {
                    min_distance[neighbor[1]] = current_distance;
                    min_heap.push({-current_distance, neighbor[1]});
                }
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (min_distance[i] == INT_MAX) {
            min_distance[i] = 0;
        }
        g << min_distance[i] << " ";
    }
    return 0;
}