#include <bits/stdc++.h>
#define DEF 50010
#define INF 50000000000

using namespace std;

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

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

int n, m;

long long D[DEF];

set < pair < int, int > > 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});
    }

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

    S.insert ({0, 1});

    while (!S.empty ()) {
        int nod = S.begin ()->second;
        S.erase (S.begin ());

        for (pair < int, int > it : L[nod]) {
            int vecin = it.first;
            int cost = it.second;
            if (D[vecin] > D[nod] + cost) {
                if (D[vecin] != INF) {
                    S.erase (S.find ({D[vecin], vecin}));
                }
                D[vecin] = D[nod] + cost;
                S.insert ({D[vecin], vecin});
            }
        }
    }

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

    return 0;
}