#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;
const int N = 50010;
vector <pii> v[N];
set <pii> S;
int n, m, dist[N];

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 (dist[it.first] != (1<<30))
                    S.erase(S.find({dist[it.first], 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, x, y, z; i<=m; i++){
        cin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    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;
}