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

using namespace std;

vector<vector<pair<int,int>>> V; // V[from] = [to, dist]

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

    int N,M;
    fin>>N>>M;
    V.resize(N);
    for(int i=0;i<M;i++) {
        int from, to, dist;
        fin>>from>>to>>dist;
        from--;
        to--;
        V[from].push_back({to, dist});
    }

    vector<int> D(N, numeric_limits<int>::max());
    D[0] = 0;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty()) {
        auto curr = Q.front();
        Q.pop();
        for(auto& item : V[curr]) {
            auto to = item.first;
            auto dist = item.second;
            if (D[curr] + dist < D[to]) {
                D[to] = D[curr] + dist;
                Q.push(to);
            }
        }
    }
    for(int i=1; i<N; i++) {
        fout<<D[i]<<' ';
    }



}