#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],f[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({0,1});
    f[1]=1;
    while(!S.empty()){
        pair<int,int>top = *S.begin();
        S.erase(S.begin());
        int nod = top.second;


        for(auto x : G[nod]){
            int vecin = x.first;
            int cost2 = x.second;
            if(dp[vecin]>dp[nod]+cost2){
            S.erase({dp[vecin],vecin});
            dp[vecin]=dp[nod]+cost2;
            S.insert({dp[vecin],vecin});

            }
        }
    }

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


    return 0;
}