#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
set<pair<int,int>>S;
int n,m,dp[100001];
vector<pair<int,int>>G[100001];

int main(){
    fin>>n>>m;
   while(m--){
        int i,j,cost;
        fin>>i>>j>>cost;
        G[i].push_back({j,cost});
    }
    for(int i=2;i<=n;i++)
            dp[i]=1000000000;
    S.insert({1,0});
    while(!S.empty()){
        pair<int,int>top = *S.begin();
        S.erase(S.begin());
        int nod = top.first;
        int cost = top.second;
        for(auto x : G[nod]){
            int vecin = x.first;
            int cost2 = x.second;
            if(dp[vecin]>cost+cost2)
            dp[vecin]=cost+cost2,S.insert({vecin,dp[vecin]});
        }
    }

    for(int i=2;i<=n;i++)
        if(dp[i]!=1000000000)
        fout<<dp[i]<<" ";
        else
            fout<<0<<" ";


    return 0;
}