#include <bits/stdc++.h>
#define DIM 50001
#define INF INT_MAX
#define int long long
using namespace std;

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

int n, m, a, b, c, cost_fiu, fiu, nod;
int drum[DIM];
int i, j;
vector <pair <int, int> > G[DIM];
set <pair <int, int> > s;

int32_t main(){
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b, c));
    }
    for(i=2; i<=n; i++)
        drum[i]=INF;
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        nod=s.begin()->second;
        s.erase(s.begin());
        for(auto k:G[nod]){
            fiu=k.first;
            cost_fiu=k.second;
            if(drum[fiu]>drum[nod]+cost_fiu){
                s.erase(make_pair(drum[fiu], fiu));
                drum[fiu]=drum[nod]+cost_fiu;
                s.insert(make_pair(drum[fiu], fiu));
            }
        }
    }
    for(i=2; i<=n; i++){
        if(drum[i]>=INF)
            drum[i]=0;
        fout<<drum[i]<<" ";
    }
}