#include <fstream>
#include <vector>
using namespace std;

const int kNMax = 50001, kInf = 0x3f3f3f3f;
int n, m, dist[kNMax], poz[kNMax], heap[kNMax],contor_heap;
vector <pair <int, int> > G[kNMax];

void Citire() {
    ifstream in("dijkstra.in");
    int n1, n2, c;
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> n1 >> n2 >> c;
        G[n1].push_back(make_pair(n2, c));
    }
    in.close();
}

void Initializare() {
    for (int i = 2; i <= n; ++i) {
        dist[i] = kInf;
        poz[i] = -1;
    }
    poz[1] = 1;
    heap[++contor_heap] = 1;
}

void DownHeap(int nod) {
    int fiu;
    while (nod <= contor_heap) {
        fiu = nod;
        if (nod * 2 <= contor_heap) {
            fiu = nod * 2;
            if (fiu + 1 <= contor_heap && dist[heap[fiu + 1]] < dist[heap[fiu]])
                    fiu++;
        }
        else
            return;
        if (dist[heap[nod]] > dist[heap[fiu]]) {
            poz[heap[nod]] = fiu;
            poz[heap[fiu]] = nod;
            swap(heap[nod], heap[fiu]);
            nod = fiu;
        }
        else
            return;
    }
}

void UpHeap(int nod) {
    int tata;
    while (nod>1) {
        tata = nod / 2;
        if (dist[heap[tata]] > dist[heap[nod]]) {
            poz[heap[tata]] = nod;
            poz[heap[nod]] = tata;
            swap(heap[tata], heap[nod]);
            nod = tata;
        }
        else
            nod = 1;
    }
}

void Solve() {
    Initializare();
    int nod, vecin, cost;
    while (contor_heap) {
        nod = heap[1];
        swap(heap[1], heap[contor_heap]);
        poz[heap[1]] = 1;
        contor_heap--;
        DownHeap(1);
        for (int i = 0; i < G[nod].size(); ++i) {
            vecin = G[nod][i].first;
            cost = G[nod][i].second;
            if (dist[vecin] > dist[nod] + cost) {
                    dist[vecin] = dist[nod] + cost;
                    heap[++contor_heap] = vecin;
                    poz[vecin] = contor_heap;
                    UpHeap(contor_heap);
                    }
            }
        }
}

void Afisare() {
    ofstream out("dijkstra.out");
    for (int i = 2; i <= n; ++i)
        if (dist[i] == kInf)
            out << 0 << ' ';
        else
            out << dist[i] << ' ';
    out << '\n';
    out.close();
}

int main () {
    Citire();
    Solve();
    Afisare();
    return 0;
}