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

typedef pair<int, int> pi;

typedef vector<int> vi;

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

vector<vector<pair<int, int>>> adjacent_list(50001);
vector<bool> visited(50001, false);
vector<int> min_distance(50001, INT_MAX);
priority_queue<pi, vector<pi>, greater<pi> > 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()) {
        pi current_node_data = min_heap.top(); // the node and its current distance
        min_heap.pop();
        int node = current_node_data.second;
        if (visited[node] == false) {
            visited[node] = true;
            for (auto neighbor: adjacent_list[node]) {
                if (visited[neighbor.second] == false) {
                    int current_distance = min_distance[node] + neighbor.first;
                    if (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;
}