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

using std::vector, std::pair;

int main(){
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");
    int n, m;
    in >> n >> m;
    vector<vector<pair<int, int>>> graph(n, vector<pair<int, int>>());  // graph[u][x] = {v, w}: u -> v w értek
    std::priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> q;     // q.front().first hova, q.front().second jelenleg milyen drága
    vector<int> distance(n, INT_MAX);
    distance[0] = 0;
    q.push({0, distance[0]});
    for(int i = 0; i < m; i++){
        int u, v, w;
        in >> u >> v >> w;
        u--; v--;
        graph[u].push_back({v, w});
    }
    while(!q.empty()){
        int curC = q.top().first, curD = q.top().second;
        q.pop();
        if(curD == distance[curC]){
            for(int i = 0; i < graph[curC].size(); i++){
                int w = graph[curC][i].first, c = graph[curC][i].second;
                if(distance[w] > curD + c){
                    distance[w] = curD + c;
                    q.push({w, distance[w]});
                }
            }
        }
    }
    for(int i = 1; i < n; i++)
        out << distance[i] << ' ';
}