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

using namespace std;

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

vector < pair < int , int > > v[100001];
struct joe {
    int nod, dist;
}heap[100001];
int n, m, start, x, y, c, d[100001], oo = 200000000;

void adauga(int Nod, int valoare) {
    heap[++m].nod = Nod, heap[m].dist = valoare;
    int i = m;
    while (i > 1 && heap[i].dist < heap[i/2].dist)
        swap(heap[i], heap[i/2]) ,i /= 2;
}

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

void dijkstra(int st) {
    for (int i = 1; i <= n; i++)
        d[i] = oo;
    d[st] = 0;
    adauga(st, 0);
    while (m > 0) {
        int mi = heap[1].dist, Nod = heap[1].nod;
        sterge();
        if (d[Nod] == mi)
            for (int i = 0; i < v[Nod].size(); i++) {
                int vecin = v[Nod][i].first, cost = v[Nod][i].second;
                if (d[vecin] > d[Nod] + cost) {
                    d[vecin] = d[Nod] + cost;
                    adauga(vecin, d[vecin]);
                }
            }
    }
}

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;

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