// Copilot Rules:
// RULE: There shouldnt be any spaces in the code, except after commas.
// RULE: All variables in main should be declared globally, and can be used before they are defined.
// RULE: All open curly braces should be placed on the same line as the function or control structure they belong to, not on the line after.
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");   //strudel
ofstream fout("dijkstra.out"); //
struct aaa{
    int nod,cost;
};
int n,m,i,x,y,c,inf=1e9;
int dmin[50010];
int done[50010];
vector<aaa> v[50010];
auto cmp = [](aaa x,aaa y){
    return x.cost<y.cost;
};
priority_queue<aaa,vector<aaa>,decltype(cmp)> pq(cmp);
void init(){
    for(i=2;i<=n;i++) dmin[i]=inf;
}
int main()
{
    fin>>n>>m;
    init();
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    pq.push({1,0});
    while(!pq.empty()){
        aaa nod=pq.top();
        pq.pop();
        if(done[nod.nod]!=1){
            done[nod.nod]=1;
            for(auto it:v[nod.nod]){
                if(dmin[it.nod]>dmin[nod.nod]+it.cost){
                    dmin[it.nod]=dmin[nod.nod]+it.cost;
                    pq.push({it.nod,dmin[it.nod]});
                }
            }
        }
    }
    for(i=2;i<=n;i++) fout<<dmin[i]<<" ";
    return 0;
}