#include <bits/stdc++.h>

#define INF 100010
#define MAX_N 50000

using namespace std;

typedef pair<int, int> int_pair;

int dist[MAX_N];
bool visited[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; visited[i] = false; }
    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();
        if (visited[min_vertex_index]) continue;
        visited[min_vertex_index] = true;

        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;
                    if (visited[curr_vertex_index]) continue;
                    min_heap.push((*i));
                }
            }
    }

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

    return 0;
}