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

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

#define pii pair<int, int>

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

bool comp(pii a, pii b){
    return a.second < b.second or (a.second == b.second and a.first < b.first);
}

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

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

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

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

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

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

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