#include <iostream>
#include "fstream"
#include "vector"
#include "queue"

std::fstream in ("dijkstra.in", std::ios::in) ;
std::fstream out ("dijkstra.out", std::ios::out) ;

const int MV = 5e4 ;
using PII = std::pair<int, int> ;

int cost[MV + 1] ;

std::vector<PII> G[MV + 1] ;

void dijkstra(int start) {
    std::priority_queue<PII, std::vector<PII>, std::greater<PII> > pq ;
    pq.push({0, start}) ;
    while (!pq.empty()) {
        PII top = pq.top() ;
        pq.pop() ;
        if (cost[top.second] != top.first) {
            continue ;
        }
        cost[top.second] = top.first ;
        for (auto it : G[top.second]) {
            if (cost[top.second] + it.second < cost[it.first]) {
                cost[it.first] = cost[top.second] + it.second ;
                pq.push({cost[it.first], it.first}) ;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m, i, x, y, c ;
    in >> n >> m ;
    for (i = 1 ; i <= m ; ++ i) {
        in >> x >> y >> c ;
        G[x].push_back({y, c}) ;
    }
    for (i = 1 ; i <= n ; ++ i) {
        cost[i] = 1e9 ;
    }
    cost[1] = 0 ;
    dijkstra(1) ;
    for (i  = 2 ; i <= n ; ++ i) {
        if (cost[i] == 1e9) {
            cost[i] = 0 ;
        }
        out << cost[i] << ' ' ;
    }
}