#include <iostream>
#include <vector>
#include <fstream>
#include <deque>

using namespace std;

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int N, M; cin >> N >> M;

    vector< vector< pair<int, int> > > E(N);
    for (int i = 0; i < M; ++i) {
        int x, y, z; cin >> x >> y >> z;
        --x; --y;
        E[x].push_back({y, z});
    }

    deque<int> D;
    vector<int> used(N, 0);
    vector<int> dis(N, 0x3f3f3f3f);
    dis[0] = 0;
    D.push_back(0);

    while (!D.empty()) {
        int x = D.front(); D.pop_front();

        used[x] = 1;
        for (auto &y : E[x])
            if (dis[x] + y.second < dis[y.first]) {
                dis[y.first] = dis[x] + y.second;
                if (not used[y.first])
                    D.push_front(y.first);
                else
                    D.push_front(y.first);
                used[y.first] = 1;
            }
    }

    for (int i = 1; i < N; ++i)
        cout << dis[i] << " ";
    cout << "\n";
}