#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];
int dist[N];

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));
    }
    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    map<int, int> nodes_costs;
    nodes_costs[1] = 0;
    while (!nodes_costs.empty()) {
        int node = nodes_costs.begin()->first;
        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) {
                dist[arrival] = dist[node] + cost;
                nodes_costs[arrival] = dist[arrival];
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) {
            fout << 0 << ' ';
        } else {
            fout << dist[i] << ' ';
        }
    }
    return 0;
}