#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector<pair<int,int>> v[50001];
priority_queue<pair<int,int>> q;
int parc[50001],dp[50001];
int main()
{
    int n,m,i,j,node,node2,cost,x,y,c;
    in>>n>>m;
    for(i=1;i<=m;++i){
        in>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(i=1;i<=n;++i)
        dp[i]=1e9;
    dp[1]=0;
    q.push(mp(0,1));
    parc[i]=1;
    while(!q.empty()){
        node=q.top().second;
        q.pop();
        if(!parc[node]){
            parc[node]=1;
            for(i=0;i<v[node].size();++i){
                node2=v[node][i].first;
                cost=v[node][i].second;
                if(dp[node]+cost<dp[node2]){
                    dp[node2]=dp[node]+cost;
                    q.push(mp(-dp[node2],node2));
                }
            }
        }
    }
    for(i=2;i<=n;++i)
        out<<dp[i]<<" ";
    return 0;
}