#include <bits/stdc++.h>

#define INF (1 << 17)

using namespace std;

typedef pair<int, int> intPair;
typedef vector< vector<int> > intMatrix;
typedef vector< vector<intPair> > intPairMatrix;

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

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

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

    vector<int> dist(n, INF);
    priority_queue< intPair, vector<intPair>, greater<intPair> > min_heap;
    min_heap.push(make_pair(0, 0));
    dist[0] = 0;

    while (!min_heap.empty()) {
        intPair min_vertex = min_heap.top();
        min_heap.pop();

        int min_vertex_weight = min_vertex.first;
        int min_vertex_i = min_vertex.second;

        vector<intPair>::iterator it;
        for (it = graph[min_vertex_i].begin();
                it != graph[min_vertex_i].end();
                it++) {
            int cvertex_weight = (*it).first;
            int cvertex_i = (*it).second;
            int sum = dist[min_vertex_i] + cvertex_weight;

            if (dist[cvertex_i] > sum) {
                dist[cvertex_i] = sum;
                min_heap.push((*it));
            }
        }
    }

    for (int i = 1; i < n; i++) {
        if (dist[i] == INF)
            dist[i] = 0;
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}