#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);

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));
    }
    dist[1] = 0;
    set<pair<int, int>> nodes_costs;
    nodes_costs.insert(make_pair(0, 1));
    while (!nodes_costs.empty()) {
        int node = nodes_costs.begin()->second;
        nodes_costs.erase(nodes_costs.begin());
        for (auto i = graf[node].begin(); i != graf[node].end(); ++i) {
            int arrival = i->first, cost = i->second;
            if (dist[arrival] > dist[node] + cost) {
                if (dist[arrival] != INF) {
                    nodes_costs.erase(nodes_costs.find(make_pair(dist[arrival], arrival)));
                }
                dist[arrival] = dist[node] + cost;
                nodes_costs.insert(make_pair(dist[arrival], arrival));
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) {
            fout << 0 << ' ';
        } else {
            fout << dist[i] << ' ';
        }
    }
    return 0;
}