#include <bits/stdc++.h>

using namespace std;
vector<pair<long long,int>> adj[100000];
int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n,m;
    long long inf=1e18;
    fin>>n>>m;
    priority_queue<pair<long long,int> ,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
    vector<long long> dist(n+1,inf);
    for(int i =0;i<m;i++){
        int u,v;
        long long w;
        fin>>u>>v>>w;
        adj[u].push_back({w,v});
    }
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        int u=pq.top().second;
        long long d=pq.top().first;
        pq.pop();
        if(dist[u]<d)continue;
        for(auto &edge:adj[u]){
            int v=edge.second;
            long long w=edge.first;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(dist[i]==inf)fout<<0<<" ";
        else fout<<dist[i]<<" ";
    }

    return 0;
}