#include<bits/stdc++.h>
using namespace std;

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

#define pii pair<int, int>

int n, m, viz[50005];
vector<pii> G[50005];
vector<int> D;

int main(){
    fin >> n >> m;

    for(;m--;){
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(c, y));
    }

    D.resize(n + 1, 1e9);
    D[1] = 0;

    set<pii> S;
    S.insert({0, 1});

    while(!S.empty()){
        int node = S.begin()->second;
        S.erase(S.begin());

        if(viz[node])
            continue;
        viz[node] = 1;

        for(pii p : G[node])
        if(D[p.second] > D[node] + p.first and !viz[p.second]){
            D[p.second] = D[node] + p.first;
            S.insert({D[p.second], p.second});
        }
    }

    for(int i = 2; i <= n; ++i)
        if(D[i] != (int)1e9)
            fout << D[i] << ' ';
        else
            fout << "0 ";
}