#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});
    while(!pq.empty()) {
        int nodeId=pq.top().second;
        int dist=pq.top().first;
        pq.pop();
        if(checked[nodeId])continue;
        checked[nodeId]=1;
        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;
}