#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, dist[250010];
vector<pair<int, int>> edges[250010];
set<pair<int, int>> s;

void dijkstra() {
    s.insert(make_pair(0, 1)); // nod, distanta pana la nod
    while (!s.empty()) {
        int node = s.begin()->second;
        s.erase(s.begin());
        for (int i = 0 ; i < edges[node].size(); ++i) {
            int vecin = edges[node][i].first;
            int cost = edges[node][i].second;
            if (dist[vecin] > dist[node] + cost) {
                if (dist[vecin] != INT_MAX) {
                    s.erase(s.find(make_pair(dist[vecin], vecin)));
                }
                dist[vecin] = dist[node] + cost;
                s.insert(make_pair(dist[vecin], vecin));
            }
        }
    }
}

int main() {
    fin.tie(0);
    ios::sync_with_stdio(0);
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        edges[x].push_back(make_pair(y, z));
    }
    for (int i = 2; i <= n; ++i) {
        dist[i] = INT_MAX;
    }
    dijkstra();
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INT_MAX) {
            dist[i] = 0;
        }
        fout << dist[i] << " ";
    }
    return 0;
}