#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;

#define N 50005
#define fi first
#define se second
int n, m, dist[N];
vector <pii> v[N];
set <pii> S;

void dijkstra(){
    for (int i=2; i<=n; i++) dist[i] = (1<<30);
    S.insert({0, 1});
    while (S.size()){
        int c = S.begin()->fi, nod = S.begin()->se;
        S.erase(S.begin());
        for (auto it: v[nod]){
            if (c + it.se < dist[it.fi]){
                if (dist[it.fi] != (1<<30)) S.erase(S.find({dist[it.fi], it.fi}));
                dist[it.fi] = c + it.se;
                S.insert({dist[it.fi], it.fi});
            }
        }
    }
}

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});
    }
    dijkstra();
    for (int i=2; i<=n; i++) cout << (dist[i] == (1<<30) ? 0 : dist[i]) << ' ';
    return 0;
}