#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector <pair < int , int > > v[50001];
int d[50001], n, m, c, x, y, oo = 2000000069;

struct joe{
    int val, nod;
}q[50001];

void adauga(int Nod, int valoare) {
    q[++m].nod = Nod, q[m].val = valoare;
    int i = m;
    while (q[i].val < q[i/2].val)
        swap(q[i], q[i/2]), i /= 2;
}

void sterge() {
    swap(q[1], q[m]);
    q[m--] = {0, 0};
    int i = 1;
    while (2 * i <= m) {
        if (q[i].val < min(q[2*i].val, q[2*i+1].val)) break;
        if (q[2*i+1].val == 0) {
            if (q[i].val <= q[2*i].val)
                break;
            else
                swap(q[i], q[2*i]), i *= 2;

        }
        else
        {
            if (q[2*i].val > q[2*i+1].val)
                swap(q[i], q[2*i+1]), i = i * 2 + 1;
            else
                swap(q[i], q[2*i]), i = i * 2;
        }
    }

}

void Dumnezeu() {
    for (int i = 2; i <= n; i++)
        d[i] = oo;
    adauga(1, 0);
    int mi, po;
    while (m) {
        mi = q[1].val, po = q[1].nod;
        sterge();
        for (int i = 0; i < v[po].size(); i++) {
            int vecin = v[po][i].first, cost = v[po][i].second;
            if (d[vecin] > d[po] + cost)
                d[vecin] = d[po] + cost, adauga(vecin, d[po] + cost);
        }
    }


    for (int i = 2; i <= n; i++)
        if (d[i] != oo)
            out << d[i] << ' ';
        else
            out << "0 ";

}

int main() {
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }
    m = 0;
    Dumnezeu();
    return 0;
}