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

const int INF = INT_MAX;

using std::pair, std::vector;

void dijkstra(int n, vector<vector<pair<int, int>>> & graf, vector<int> & dist) {
    std::priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> q; // {dist[i], i}
    dist[0] = 0;
    q.push({dist[0], 0});
    while(!q.empty()) {
        pair<int, int> top = q.top(); // top.first = dist, top.second = u
        q.pop();
        if(top.first == dist[top.second]) {
            for(auto & e : graf[top.second]) {
                if(top.first + e.second < dist[e.first]) {
                    dist[e.first] = top.first + e.second;
                    q.push({dist[e.first], e.first});
                }
            }
        }
    }
}

int main() {
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");
    int n, m;
    in >> n >> m;
    vector<vector<pair<int, int>>> graf(n);
    vector<int> dist(n, INF);
    
    while(m--) {
        int u, v, w;
        in >> u >> v >> w; u--; v--;
        graf[u].push_back({v, w});
    }
    in.close();
    dijkstra(n, graf, dist);
    for(int i = 1; i < n; i++)
        out << dist[i] << ' ';
    out.close();
}