#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ll;
typedef pair < int , int > PII;
typedef pair < int , PII >  PIPII;

int n, m, dist[50100];

priority_queue < PII > H;
vector < PII > V[50100];

void Dijkstra(int src){
    H.push({0, src});

    while (H.size()){
        int x = H.top().second; H.pop();
        
        for (auto it : V[x]){
            if (dist[it.first] > dist[x] + it.second){
                dist[it.first] = dist[x] + it.second;
                H.push({dist[it.first], it.first});
            }
        }
    }
}

int main(){
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x, y, c; i <= m; i++){
        cin >> x >> y >> c;
        V[x].push_back({y, c});
    }

    for (int i = 2; i <= n; i++) dist[i] = 2e9;

    Dijkstra(1);

    for (int i = 2; i <= n; i++)
        cout << (dist[i] == 2e9 ? 0 : dist[i]) << " ";
    return 0;
}