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

using std::vector, std::pair;

void dijkstra(int n, vector<vector<std::pair<int, int>>> & graf, vector<int> & dist) {
    dist[0] = 0;
    std::priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> q;
    q.push({dist[0], 0});

    while(!q.empty()) {
        int u = q.top().second, currDist = q.top().first;
        q.pop();
        if(currDist == dist[u]) {
            for(const auto & e : graf[u]) {
                int v = e.first, w = e.second;
                if(currDist + w < dist[v]) {
                    dist[v] = currDist + w;
                    q.push({dist[v], v});
                }
            }
        }
    }
}

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