#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
ifstream ci("dijkstra.in");
ofstream cou("dijkstra.out");

struct date{
    int nod,cost;
    inline bool operator <(const date &A)const{
        return cost>A.cost;
    }
};

int n,m;
int vis[50010],dp[50010];
vector<date>v[250010];
priority_queue<date>q;

void citire(){
    ci>>n>>m;
    date p;
    int r;
    for(int i=1;i<=m;i++){
        ci>>r>>p.nod>>p.cost;
        v[r].push_back(p);
    }
}

void init(){
    for(int i=2;i<=n;i++){
        dp[i]=INF;
    }
}

void Dijkstra(){
    date w;
    w.nod=1;
    w.cost=0;
    q.push(w);
    while(!q.empty()){
        //cout<<"k";
        w=q.top();
        q.pop();
        if(vis[w.nod]==0){
            vis[w.nod]=1;
            for(auto i:v[w.nod]){

                if(dp[i.nod]>dp[w.nod]+i.cost){
                    dp[i.nod]=dp[w.nod]+i.cost;
                    i.cost=dp[i.nod];
                    q.push(i);
                }
            }
        }
    }

}

void afis(){
    for(int i=2;i<=n;i++){
        if(dp[i]==INF){
            cou<<"0 ";
        }else{
            cou<<dp[i]<<" ";
        }

    }
}

int main()
{
    citire();
    init();
    Dijkstra();
    afis();
    return 0;
}