#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 {
    int dist=INT32_MAX;
    vector<Edge> edges;
};

int n, m, a, b, c;
bool checked[50001];
Node nodes[50001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, 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});
    }
    pq.push({0, 1});
    nodes[1].dist = 0;
    while(!pq.empty()) {
        auto [dist, nodeId] = pq.top();
        pq.pop();
        if (checked[nodeId]) continue;
        checked[nodeId] = true;
        nodes[nodeId].dist = dist;

        for (auto e : nodes[nodeId].edges) {
            if (!checked[e.neighbourId]) {
                pq.push({dist + e.cost, e.neighbourId});
            }
        }
    }
    for(int i=2;i<=n;i++) {
        cout<<nodes[i].dist<<' ';
    }
    return 0;
}