#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int NMAX=50000;
vector<pair<int, int>> g[NMAX+1];
int dist[NMAX+1];
int main () {
    int n,m,i,u,v,w,src,d,u;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin >> n >> m;
    for (i = 0; i < m; i ++) {
        cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(i=1;i<=n;++i)
        dist[i] = INF;
    src=1;
    dist[src]=0;
    pq.push({0,src});
    while(!pq.empty()) {
        d=pq.top().first;
        u=pq.top().second;
        pq.pop();
        if(d>dist[u])
            continue;
        for(i=0;i<g[u].size();++i){
            v=g[u][i].first;
            w=g[u][i].second;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    for(i=2;i<=n;i++)
        cout << (dist[i]==INF?0:dist[i]) << " ";
    return 0;
}