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

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

std::vector<int> dijkstra(std::vector<std::vector<std::pair<int, int>>> const &adj) {
    const int INF = INT_MAX;
    std::vector<int> distances(adj.size(), INF);
    distances[0] = 0;
    std::priority_queue<std::pair<int,int>> pq;
    pq.emplace(0, 0);
    std::vector<bool> processed(adj.size(), false);
    while(!pq.empty()) {
       const int node = pq.top().second;
       pq.pop();
       if(processed[node])
           continue;
       processed[node] = true;
       for(auto p : adj[node]) {
            const int n = p.first, w = p.second;
            distances[n] = std::min(distances[n], distances[node]+w);
            pq.emplace(-distances[n], n);
       }
    }

    for(auto &d : distances)
        if(d==INF)
            d=0;
    return distances;
}

int main() {
    int n, m, s;
    fin >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    while(m--) {
        int a, b, w;
        fin >> a >> b >> w;
        a--, b--;
        adj[a].emplace_back(b, w);
    }

    const auto distances = dijkstra(adj);
    std::copy(distances.begin()+1, distances.end(),
              std::ostream_iterator<int>(fout, " "));
    return 0;
}