#include <bits/stdc++.h>

using namespace std;

#define INF (1 << 17)

int n, m;
vector< vector< pair<int, int> > > graph;
vector< int > dist;

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

    cin >> n >> m;
    graph.reserve(n + 5);
    dist.reserve(n + 5);

    for (int i = 0, x, y, z; i < m; i++) {
        cin >> x >> y >> z;
        graph[x].push_back(make_pair(y, z));
    }

    for (int i = 2; i <= n; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;

    set< pair<int, int> > nodes;
    nodes.insert(make_pair(0, 1));
    while (!nodes.empty()) {
        int node = nodes.begin()->second;
        int cdist = nodes.begin()->first;
        nodes.erase(nodes.begin());

        for (int i = 0;
                i < graph[node].size();
                i++) {
                    int dest_node = graph[node][i].first;
                    int cost = graph[node][i].second;
                    if (dist[dest_node] > dist[node] + cost) {
                        if (dist[dest_node] != INF) {
                            nodes.erase(nodes.find(make_pair(dist[dest_node], dest_node)));
                        }
                        dist[dest_node] = dist[node] + cost;
                        nodes.insert(make_pair(dist[dest_node], dest_node));
                    }
                }
    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] == INF) {
            dist[i] = 0;
        }
        cout << dist[i] << ' ';
    }
    cout << '\n';

    return 0;
}