#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <tuple>


const int MAXN = 50001;

using namespace std;

typedef pair<int,int> pii;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n,m,dp[MAXN];
vector<pii>graf[MAXN];
priority_queue<pii,vector<pii>,greater<pii>>coada;

void solve(){
    dp[1] = 0;
    for(int i = 2; i <= n; i++)
        dp[i] = 1e9;
    coada.push(make_pair(0,1));
    while(coada.size()){
        auto top = coada.top();
        int cost = top.first;
        int nod = top.second;

        coada.pop();
        if(dp[nod] != cost)
            continue;


        for(auto muchie : graf[nod]){
            int vecin = muchie.first,cost_muchie = muchie.second;
            if(dp[nod] + cost_muchie < dp[vecin]){
                dp[vecin] = dp[nod] + cost_muchie;
                coada.push({dp[vecin],vecin});
            }
        }
    }
    for(int i = 2; i <= n; i++)
        if(dp[i] == 1e9)
            dp[i] = 0;
    for(int i = 2; i <= n; i++)
        out<<dp[i]<<" ";
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,cost;
        in>>x>>y>>cost;
        graf[x].push_back({y,cost});
//        graf[y].push_back({x,cost});
//        cout<<x<<" "<<y<<endl;
    }
    solve();
    return 0;
}