#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std ;

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

struct muchie {
    int j ;
    int cost ;
};

const int NMAX = 50005 ;
const int INF = INT_MAX ;
int n , m ;
int d[NMAX] , viz[NMAX] ;

vector<muchie> g[NMAX] ;

struct comp {
    bool operator()(int x , int y) {
        return d[x] > d[y] ;
    }
};

priority_queue<int , vector<int> , comp> coada ;

void dijkstra(int nodStart) {

    d[nodStart] = 0 ;
    coada.push(nodStart) ;
    viz[nodStart] = 1 ;

    while (!coada.empty()) {
        int nou = coada.top() ;
        coada.pop() ;
        viz[nou] = 0 ;

        for(int i = 0 ; i< g[nou].size() ; i++) {
            int x = g[nou][i].j ;
            int cost = g[nou][i].cost ;
            if(d[nou] + cost < d[x]) {
                d[x] = d[nou] + cost ;
                if(!viz[x]) {
                    coada.push(x) ;
                    viz[x] = 1 ;
                }
            }
        }
    }
}

int main()
{

    fin >> n >> m ;
    for(int i = 1 ; i<=m ; i++) {
        int x, y , cost ;
        fin >> x >> y >> cost ;
        muchie a ;
        a.j = y ;
        a.cost = cost ;
        g[x].push_back(a) ;
    }

    for(int i = 1 ; i<=n ; i++) {
        d[i] = INF ;
    }

    dijkstra(1) ;

    for(int i = 2 ; i<=n ; i++) {
        if(d[i] != INF)
            fout << d[i] << ' ' ;
        else fout << "0 " ;
    }
    return 0;
}