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

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]});

    while(m--){
        int u, v, w;
        in >> u >> v >> w;
        u--; v--;
        graph[u].push_back({v, w});
    }

    while(!q.empty()){
        int curU = q.top().first, curD = q.top().second;
        q.pop();
        if(curD == distance[curU]){
            for(auto e : graph[curU]){
                int v = e.first, w = e.second;
                if(distance[v] > curD + w){
                    distance[v] = curD + w;
                    q.push({v, distance[v]});
                }
            }
        }
    }
    for(int i = 1; i < n; i++)
        if(distance[i] == INT_MAX)
            out << 0 << ' ';
        else
            out << distance[i] << ' ';
}