#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int N, M;
vector<pair<int, int>> g[50005]; // first este vecinul, second este costul muchiei
int d[50005], parent[50005]; // d[i] distanta de la 1 la i
bool fixat[50005]; // initial fixat[i] = false pentru toti i

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

    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }

    d[1] = 0;
    for (int i = 2; i <= N; ++i)
        d[i] = INF;

    while (true) {
        int cost_minim = INF, pos_minim;
        for (int i = 1; i <= N; ++i)
            if (!fixat[i] && d[i] < cost_minim) {
                cost_minim = d[i];
                pos_minim = i;
            }
        if (cost_minim == INF)
            break;

        int nod = pos_minim;
        fixat[nod] = true;
        for (pair<int, int> p : g[nod]) {
            int vecin = p.first;
            int cost_muchie = p.second;
            if (d[vecin] > d[nod] + cost_muchie) {
                d[vecin] = d[nod] + cost_muchie;
                parent[vecin] = nod;
            }
        }
    }

    for (int i = 2; i <= N; ++i) {
        if (d[i] == INF)
            cout << "0 ";
        else
            cout << d[i] << " ";
    }

    // for (int nod = 5; nod != 0; nod = parent[nod]) {
    //     cout << "\n" << nod;
    // }

    return 0;
}