#include <iostream>
#include <algorithm>
#include <list>
#include <set>
#include <fstream>
#include <vector>
#define INF 100000001
using namespace std;
//ifstream in("input.in");
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector< list<pair<long long, long long> > > v;
vector<long long> d, viz, pred;
set< pair<long long, long long> > Q;
int n, m, x, y, c;
int main(){
    in >> n >> m;
    v.resize(n+1);
    d.resize(n+1);
    pred.resize(n+1);
    viz.resize(n+1);
    for(int i=1;i<=m;i++){
        in >> x >> y >> c;
        v[x].push_back({c,y});
        //v[y].push_back({c,x});
    }
    for(int i=1;i<=n;i++) d[i] = INF;

    d[1] = 0;
    Q.insert({d[1],1});
    while(!Q.empty()){
        int K = Q.begin()->second;
        Q.erase(Q.begin());
        if(!viz[K]){
            viz[K] = 1;
            for(auto i : v[K]){
                if(d[i.second] > d[K] + i.first){
                    d[i.second] = d[K] + i.first;
                    Q.insert({d[i.second], i.second});
                }
            }
        }
    }
    for(int i=2; i<=n; i++){
        out << d[i] << " ";
    }
    return 0;
}