#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int> > a[50001];
int dist [50001];
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
 
int main(){
    int n,m;
    in >> n >> m;
    for (int i = 1; i <= n; i++){
        dist[i] = 1e9;
    }
    for (int i = 0; i < m; i++){
        int x,y,cost;
        in >> x >> y >> cost;
        a[x].push_back({cost, y});  
    }
    set <pair <int, int> > s;
    dist[1] = 0;
    s.insert({0, 1});
    while (!s.empty()) {
        int node = s.begin()->second;
        s.erase(s.begin());
        for (auto next: a[node]) {
            int cost = next.first;
            int next_node = next.second;
            int urmatoarea = dist[node] + cost;
            if (urmatoarea < dist[next_node]) {
                s.erase({dist[next_node], next_node});
                dist[next_node] = urmatoarea;
                s.insert({dist[next_node], next_node});
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (dist[i] == 1e9) {
            out << "0 ";
        }
        else {
            out << dist[i] << " ";
        }
    }
}