#include <fstream>
#include <vector>
#include <queue>

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

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

struct cmp{
    bool operator()(pii a, pii b){
        return a.second < b.second;
    }
};

int N, M;
std::vector<std::vector<pii> > G;
std::priority_queue<pii, std::vector<pii>, cmp> pq;
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;
    pq.push({1, 0});

    while(!pq.empty()){
        int node = pq.top().first;
        pq.pop();

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

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