#include <bits/stdc++.h>

using namespace std;

struct NOD {
    int value;
    int pos;
};

int n, m, a, b, d;
int MARE = 1000000000;
int dist[50001];
bool parcurs[50001];
vector<int> v[50001], c[50001];
priority_queue<NOD> pq;

bool operator<(const NOD& a, const NOD& b) {
    return (a.value > b.value);
}

void dijkstra() {
    for (int i = 1; i <= n; ++i) dist[i] = MARE;
    NOD nod = { 0,1 };
    dist[1] = 0;
    pq.push(nod);

    while (not pq.empty()) {
        nod = pq.top();
        pq.pop();
        int value = nod.value, pos = nod.pos, vecin;
        if (parcurs[pos]) continue;
        parcurs[pos] = true;

        for (int i = 0; i < v[pos].size(); ++i) {
            vecin = v[pos][i];
            if (dist[vecin] > value + c[pos][i] and not parcurs[vecin])
                dist[vecin] = value + c[pos][i], pq.push({ dist[vecin],vecin });
        }

    }
}

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

    in >> n >> m;

    for (int i = 0; i < m; ++i) {
        in >> a >> b >> d;
        v[a].push_back(b), c[a].push_back(d);
    }

    dijkstra();

    for (int i = 2; i <= n; ++i) out << ((dist[i] == MARE) ? 0 : dist[i]) << ' ';

    in.close(), out.close();
}