#include <bits/stdc++.h>
using namespace std;

int n, m, dist[50010];
vector <pair<int,int> > V[50010];
set <pair<int,int> > S;

void dijkstra(){
    S.insert({0,1});
    while (S.size()){
        int nod = S.begin()->second, c = S.begin()->first;
        S.erase(S.begin());
        for (auto it: V[nod]){
            if (c + it.second < dist[it.first]){
                if (S.find({(1<<30), it.first}) != S.end()){
                    S.erase(S.find({(1<<30), it.first}));
                }
                dist[it.first] = c + it.second;
                S.insert({dist[it.first], it.first});
            }
        }
    }
}

int main(){
    ifstream cin ("dijkstra.in");
    ofstream cout ("dijkstra.out");
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        V[x].push_back({y, cost});
    }
    for (int i=2; i<=n; i++) dist[i] = (1<<30);
    dijkstra();
    for (int i=2; i<=n; i++) cout << (dist[i] == (1<<30) ? 0 : dist[i]) << " ";
    return 0;
}