#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void solve(int n,const vector<vector<pair<int,int>>>&graf){
    using P=pair<int,int>;
    priority_queue<P,vector<P>,greater<P>>pq_min;
    vector<int>dist(n+1,2000000000);
    dist[1]=0;
    pq_min.push({0,1});
    while(!pq_min.empty()){
        P u=pq_min.top();
        int dis=u.first;
        int cur=u.second;
        pq_min.pop();
        if(dis>dist[cur]){
            continue;
        }
        for(auto vecin:graf[cur]){
            int v=vecin.first;
            int cost=vecin.second;
            if(dist[cur]+cost<dist[v]){
                dist[v]=dist[cur]+cost;
                pq_min.push({dist[v],v});
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(dist[i]==2000000000){
            out<<0<<" ";
        }else{
            out<<dist[i]<<" ";
        }
    }
}

int main(){
    int n,m,x,y,len;
    in>>n>>m;
    vector<vector<pair<int,int>>>graf(n+1);
    for(int i=1;i<=m;i++){
        in>>x>>y>>len;
        graf[x].push_back({y,len});
    }
    solve(n,graf);
}