#include <iostream>
#include <bits/stdc++.h>
using namespace std;

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

typedef pair<int, int> path_info;
const int max_nodes = 50001;

vector<vector<pair<int, int>>> adjacent_list(max_nodes);
vector<bool> visited(max_nodes, false);
vector<int> min_distance(max_nodes, INT_MAX);
priority_queue<path_info, vector<path_info>, greater<path_info>> min_heap;

int main() {
    int n, m;
    f >> n >> m;
    min_heap.push(make_pair(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(make_pair(distance, y));
    }
    while (!min_heap.empty()) {
        path_info current_node_data = min_heap.top(); // the node and its current distance
        min_heap.pop();
        int node = current_node_data.second;
        if (visited[node] == true) {
            continue;
        }
        visited[node] = true;
        for (auto neighbor: adjacent_list[node]) {
            int current_distance = min_distance[node] + neighbor.first;
            if (visited[neighbor.second] == false && current_distance < min_distance[neighbor.second]) {
                min_distance[neighbor.second] = current_distance;
                min_heap.push(make_pair(current_distance, neighbor.second));
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (min_distance[i] == INT_MAX) {
            min_distance[i] = 0;
        }
        g << min_distance[i] << " ";
    }
    return 0;
}