// dijkstra pe graf orientat
#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin ("dijkstra.in");
std::ofstream fout ("dijkstra.out");

int const INF = 1e8; // infinity
int const nmax = 50005; // noduri
int const mmax = 250005; // muchii

struct drum {
    int nodf; // nodul "final" la care se ajunge prin luarea acestui drum
    int cost; // cost drum
};

// graf
std::vector <drum> adjacency[nmax]; // pentru fiecare nod colectionam drumurile care "incep" la el

// dijkstra
bool check[nmax]; // nod vericat?
int lungime[nmax]; // lungime[nod] = lungimea drumului 1 - nod
struct pq_elem {
    int nod; // nodul

    bool operator < (pq_elem const other) const {
        return lungime[nod] > lungime[other.nod];
    }
};
std::priority_queue <pq_elem> pq;

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = m; i; i--) {
        int nod_start, nod_end, cost;
        fin >> nod_start >> nod_end >> cost;
        adjacency[nod_start].push_back({nod_end, cost});
    }
    for (int i = 2; i <= n; i++)
        lungime[i] = INF;
    pq.push({1});
    while (!pq.empty()) {
        int top = pq.top().nod;
        pq.pop();
        if (check[top]) continue; // daca nodul a fost deja verificat (pentru ca avem pq), nodul are un cost mai mic deja gasit => skip
        else check[top] = true; // daca nu, notam ca i-a fost gasita lungimea minima si ca a fost vizitat
        int cnt_vector = adjacency[top].size();
        for (int i = 0; i < cnt_vector; i++) {
            if (check[adjacency[top][i].nodf] == false && lungime[top] + adjacency[top][i].cost < lungime[adjacency[top][i].nodf]) {
                lungime[adjacency[top][i].nodf] = lungime[top] + adjacency[top][i].cost;
                pq.push({adjacency[top][i].nodf});
            }
        }
    }
    for (int i = 2; i <= n; i++)
        fout << lungime[i] << " ";
    return 0;
}