#include <fstream>
#include <vector>
#include <set>
#define INF 1 << 29
#define DEF 50010

using namespace std;

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

int n, m, st, D[DEF];

vector < pair < int, int > > L[DEF];

struct compare {
    bool operator() (const int a, const int b) {
        return D[a] < D[b];
    }
};

set < int, compare > S;

int main () {

    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back ({y, c});
       // L[y].push_back ({x, c});
    }

    for (int i = 0; i <= n; ++ i) {
        D[i] = INF;
    }

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

    while (! S.empty ()) {
        int curr = * S.begin ();
        S.erase (S.begin ());

        for (int i = 0; i < L[curr].size (); ++ i) {
            if (D[L[curr][i].first] > D[curr] + L[curr][i].second) {
                if (D[L[curr][i].first] != INF) {
                    S.erase (S.lower_bound (curr));
                }
                D[L[curr][i].first] = D[curr] + L[curr][i].second;
                S.insert (L[curr][i].first);
            }
        }
    }

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

}