#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
ifstream ci("dijkstra.in");
ofstream cou("dijkstra.out");
struct date{
    int nod,cost;
};
int n,m;
int vis[50010],dp[50010];
vector<date>v[250010];
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.front();
        q.pop();
        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++){
        cou<<dp[i]<<" ";
    }
}

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