#include <bits/stdc++.h>
#define ll long long

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m;
set<pair<int,int>>s;
vector<pair<int,int>>G[100001];
int dp[100001];

int main(){
    fin>>n>>m;
    for(int i = 1;i<=m;i++){
        int x,y, cost;
        fin>>x>>y>>cost;
        G[x].push_back({y,cost});
       // G[y].push_back({x,cost});
    }
    for(int i = 2;i<=n;i++)
        dp[i]=1000000000;
    s.insert({0,1}); // cost 0, nodul 1

    while(!s.empty()){
        pair<int,int>aux = *s.begin();
        s.erase(s.begin());
        int nod = aux.second;
        for(auto x : G[nod]){
            int vecin = x.first;
            int cost = x.second;
            // dp[vecin] es costul lui vecin
            if(dp[vecin]>dp[nod]+cost){
                // sterg daca e deja in set
                s.erase({dp[vecin],vecin});
                s.insert({dp[nod]+cost,vecin});
                dp[vecin]=dp[nod]+cost;
            }
        }
        }
    for(int i = 2; i <=n; i++){

        if(dp[i]!=1000000000)
            fout<<dp[i]<<" ";
        else
            fout<<0<<' ';
    }
   return 0;
}