#include <bits/stdc++.h>

using namespace std ;
ifstream f ("dijkstra.in") ;
ofstream g ("dijkstra.out") ;

void Read(int &N,int &M,vector < vector <pair <int, int> > > &G) {
    f >> N >> M ;
    for(int i=1; i<=M; i++) {
        int x, y, cost ;
        f >> x >> y >> cost ;
        G [x].push_back ({y, cost }) ; } }

vector<int> Dijkstra(int N,vector < vector <pair <int, int> > > &G,int startPoint) {
    auto comp = [](pair <int, int> A, pair <int, int> B) {
        return A.second > B.second ; };
    priority_queue < pair <int, int>, vector < pair <int, int> >, decltype (comp)> PQ (comp) ;
    vector <int> D (N + 1, INT_MAX) ;
    D [startPoint] = 0 ;
    PQ.push({startPoint, 0 }) ;
    while (!PQ.empty()) {
        auto current = PQ.top () ;
        PQ.pop () ;
        if (D [current.first] != current.second) continue ;
        for (auto next: G [current.first]) {
            if (D [next.first] > D [current.first] + next.second) {
                D [next.first] = D [current.first] + next.second ;
                PQ.push ({next.first, D [next.first] }) ; } } }
    return D; }

void Write(vector <int> D) {
    for (int i = 2 ; i < D.size() ; ++ i)
        g << ((D [i] >= INT_MAX) ? 0 : D [i]) << ' ' ; }

int main() {
    int N, M;
    vector < vector <pair <int, int> > > G (50001) ;
    Read(N,M,G);
    Write(Dijkstra(N,G,1)); }