#include <fstream>
#include <vector>
#include <queue>
#include <cstdint>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct Edge {
    int neighbourId;
    int cost;
};

struct Node {
    long long dist = INT64_MAX;
    vector<Edge> edges;
};

int n, m, a, b, c;
bool checked[50001];
Node nodes[50001];
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        nodes[a].edges.push_back({b, c});
    }
    nodes[1].dist = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        int nodeId = pq.top().second;
        long long dist = pq.top().first;
        pq.pop();
        if (checked[nodeId]) continue;
        checked[nodeId] = 1;
        nodes[nodeId].dist = dist;
        for (auto e : nodes[nodeId].edges) {
            if (dist + e.cost < nodes[e.neighbourId].dist) {
                nodes[e.neighbourId].dist = dist + e.cost;
                pq.push({nodes[e.neighbourId].dist, e.neighbourId});
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if(nodes[i].dist==INT64_MAX) {cout << "0 ";continue;}
        cout << nodes[i].dist << ' ';
    }
    return 0;
}