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

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

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

void dijkstra(){
    for(i=2; i<=n; i++)
        drum[i]=INT_MAX;
    s.insert(make_pair(0, 1));
    while(!s.empty()){
        int nod=s.begin() -> second;
        s.erase(s.begin());
        for(auto k:G[nod]){
            int fiu=k.first;
            int 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));
            }
        }
    }
}

int32_t main(){
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b, c));
    }
    dijkstra();
    for(i=2; i<=n; i++){
        if(drum[i]>=INT_MAX)
            drum[i]=0;
        fout<<drum[i]<<" ";
    }
}