#include <fstream>
#include <vector>
#include <set>

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

typedef std::pair<int, int> pii;
const int INF = 1e9;

int N, M;
std::vector<std::vector<pii> > G;
std::set<pii> S;
std::vector<int> D;

int main(){
    fin >> N >> M;

    G.resize(N + 1);
    D.resize(N + 1, INF);

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

    D[1] = 0;
    S.insert({1, 0});

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

        for(auto [y, c] : G[node]){
            if(D[y] > D[node] + c){
                D[y] = D[node] + c;
                S.insert({y, D[y]});
            }
        }
    }

    for(int i = 2; i <= N; ++i){
        if(D[i] == INF){
            fout << "0 ";
        }
        else{
            fout << D[i] << ' ';
        }
    }
}