#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<pair<int,int>> adj[50001];
int dist[50001];

int main() {
    ifstream fin("dijkstra.in");
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

    fin>>n>>m;

    int a,b,c;

    for (int i=1;i<=m;i++) {
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }

    for (int i=1;i<=n;i++) dist[i]=INT_MAX;

    pq.push({0,1});
    dist[1]=0;

    while (pq.size()>0) {
        pair<int,int> p =pq.top();
        pq.pop();

        if (p.first!=dist[p.second]) continue;

        for (auto [nod,pondere]:adj[p.second]) {
            if (dist[p.second]+pondere<dist[nod]) {
                dist[nod]=dist[p.second]+pondere;
                pq.push({dist[nod],nod});
            }

        }

    }

    for (int i=2;i<=n;i++) {
        if (dist[i]!=INT_MAX) cout<<dist[i]<<' ';
        else cout<<0<<' ';
    }

}