#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({1,0});
    f[1]=1;
    while(!S.empty()){
        pair<int,int>top = *S.begin();
        S.erase(S.begin());
        int nod = top.first;
        int cost = top.second;
        f[nod]=0;
        for(auto x : G[nod]){
            int vecin = x.first;
            int cost2 = x.second;
            if(dp[vecin]>cost+cost2){
            dp[vecin]=cost+cost2;
            if(f[vecin]==0)
                S.insert({vecin,dp[vecin]}),f[vecin]=1;

            }
        }
    }

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


    return 0;
}