#include <bits/stdc++.h>

using namespace std ;
int num_nodes;
int num_edges;
auto comp = [](pair <int, int> a, pair <int, int> b) {
    return a.second > b.second ;
};
vector < vector <pair <int, int> > > adj(50001) ;
priority_queue < pair <int, int>, vector < pair <int, int> >, decltype (comp)> dijkstra (comp) ;
vector <int> dist(50001, INT_MAX) ;

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    fin >> num_nodes >> num_edges ;
    for(int i=1; i<=num_edges; i++) {
        int src, dest, cost ;
        fin >> src >> dest >> cost ;
        adj[src].push_back ({dest, cost}) ;
    }

    dist[1]=0;
    dijkstra.push({1,0}) ;
    while (!dijkstra.empty()) {
        auto current=dijkstra.top();
        dijkstra.pop();
        if (dist[current.first]!=current.second)
            continue;
        for (auto next:adj[current.first]) {
            if (dist[next.first]>dist[current.first]+next.second) {
                dist[next.first]=dist[current.first]+next.second;
                dijkstra.push({next.first,dist[next.first]});
            }
        }
    }
    for (int i=2; i<dist.size(); i++)
        fout << ((dist [i] >= INT_MAX) ? 0 : dist [i]) << ' ' ;

    return 0;
}