#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int const N = 50005, INF = 1e9 + 9;
vector<pair<int, int>> graf[N];
vector<int> dist(N, INF);

void dijkstra() {
    dist[1] = 0;
    multimap<int, int> nodes_costs;
    nodes_costs.insert({0, 1});
    while (!nodes_costs.empty()) {
        int node = nodes_costs.begin()->second;
        nodes_costs.erase(nodes_costs.begin());
        for (int i = 0; i < graf[node].size(); ++i) {
            int arrival = graf[node][i].first, cost = graf[node][i].second;
            if (dist[arrival] > dist[node] + cost) {
                if (dist[arrival] != INF) {
                    nodes_costs.erase(nodes_costs.find(dist[arrival]));
                }
                dist[arrival] = dist[node] + cost;
                nodes_costs.insert({dist[arrival], arrival});
            }
        }
    }
}
int main() {
    int n, m; fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int src, dest, dis;
        fin >> src >> dest >> dis;
        graf[src].push_back(make_pair(dest, dis));
    }
    dijkstra();
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) {
            fout << 0 << ' ';
        } else {
            fout << dist[i] << ' ';
        }
    }
    return 0;
}