#include <bits/stdc++.h>
#define INF 99999999

using namespace std;

int main() {

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

    {
        int N; in >> N;
        int M; in >> M;
        vector<vector<pair<int, int>>> G(N);

        for (int i = 0; i < M; ++i) {
            int a; in >> a; a -= 1;
            int b; in >> b; b -= 1;
            int w; in >> w;
            G.at(a).push_back({b, w});
        }

        vector <int> D(N, INF);
        set<pair<int, int>> pq;
        pq.insert({0, 0});
        D.at(0) = 0;

        while (!pq.empty()) {
            int x = pq.begin()->second;
            pq.erase(pq.begin());

            for (int i = 0; i < G.at(x).size(); ++i) {
                int y = G.at(x).at(i).first;
                int w = G.at(x).at(i).second;
                if (D.at(x) + w < D.at(y)) {
                    if (D.at(y) < INF) {
                        pq.erase(pq.find({D.at(y), y}));
                    }
                    D.at(y) = D.at(x) + w;
                    pq.insert({D.at(y), y});
                }
            }
        }

        for (int i = 1; i < N; ++i) {
            if (D.at(i) == INF) {
                out << "0 ";
            } else {
                out << D.at(i) << " ";
            }
        }
        out << "\n";
    }

    in.close();
    out.close();

  return 0;
}