#include <bits/stdc++.h>

#define INF (1 << 17)
#define MAX_N 50000

using namespace std;

typedef pair<int, int> int_pair;

int dist[MAX_N];
vector<int_pair> graph[MAX_N];
priority_queue< int_pair, vector<int_pair>, greater<int_pair> > min_heap;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) dist[i] = INF;
    for (int i = 0, to, from, cost; i < m; i++) {
        cin >> from >> to >> cost;
        graph[from - 1].push_back(make_pair(cost, to - 1));
    }

    min_heap.push(make_pair(0, 0));
    dist[0] = 0;

    int min_vertex_index;
    int curr_vertex_index;
    int curr_vertex_weight;
    int dist_sum;
    while (!min_heap.empty()) {
        min_vertex_index = min_heap.top().second;
        min_heap.pop();

        for (vector<int_pair>::iterator i = graph[min_vertex_index].begin();
            i != graph[min_vertex_index].end();
            i++) {
                curr_vertex_index = (*i).second;
                curr_vertex_weight = (*i).first;

                dist_sum = dist[min_vertex_index] + curr_vertex_weight;
                if (dist[curr_vertex_index] > dist_sum) {
                    dist[curr_vertex_index] = dist_sum;
                    min_heap.push((*i));
                }
            }
    }

    for (int i = 1; i < n; i++) {
        cout << dist[i] << " ";
    }
    cout << "\n";

    return 0;
}