#include <cstdio>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int MAX = 50001;

struct comp {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> Q;
vector<pair<int, int>> G[MAX];

int D[MAX];  //retine costul minim al drumului pana la fiecare nod, care trece doar prin nodurile vizitate
int N, M;
bool viz[MAX];

void dijkstra() {
    viz[1] = true;
    while (!Q.empty()) {
        int x = Q.top().first;
        int d = Q.top().second;
        Q.pop();
        if (viz[x])
            continue;
        for (auto m : G[x]) {
            int y = m.first;
            int cost = m.second;
            if (!viz[y] && D[x] + cost < D[y]) {
                D[y] = D[x] + cost;
                Q.push({y, D[y]});
            }
        }
        viz[x] = true;
    }
}

int main() {
    int x, y, cost;
    in >> N >> M;
    for (int i = 1; i <= N; i++)
        D[i] = 1000000;
    D[1] = 0;
    for (int i = 1; i <= M; i++) {
        in >> x >> y >> cost;
        G[x].push_back(pair<int, int>(y, cost));
        if (x == 1) {
            D[y] = cost;
            Q.push(pair<int, int>(y, D[y]));
        }
    }

    dijkstra();

    for (int i = 2; i <= N; i++)
        if (D[i] < 1000000)
            out << D[i] << ' ';
        else
            out << 0 << ' ';

    return 0;
}