#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#include <fstream>

#define INF 1000000000
using namespace std;
int ans[50005];

vector<pair<int, int> > nodes[50005];
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        if (ans[top.second] != top.first)
            continue;
        ans[top.second] = top.first;
        for (auto node : nodes[top.second]) {
            if (ans[top.second] + node.second < ans[node.first]) {
                ans[node.first] = ans[top.second] + node.second;
                pq.push(make_pair(ans[node.first], node.first));
            }
        }
    }
}
int main() {
    int n, m, x, y, c;
    in >> n >>m;
    for (int i = 1; i <= m; ++i) {
        in >> x >> y >>c;
        nodes[x].emplace_back(make_pair(y, c));
    }
    for (int i = 2; i <= n; ++i) {
        ans[i] = INF;
    }
    dijkstra(1);
    for (int i = 2; i <= n; ++i) {
        out << (ans[i] == INF ? 0 : ans[i]) << " ";
    }
}