// dijkstra pe graf orientat
#include <fstream>
#include <vector>
#include <queue>
typedef long long ll;
std::ifstream fin ("dijkstra.in");
std::ofstream fout ("dijkstra.out");

ll const INF = 1e10; // 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 verificat?
ll length[nmax]; // length[nod] = lungimea drumului 1 - nod
struct pq_elem {
    int nod; // nodul
    ll lungime;

    bool operator < (pq_elem const other) const {
        return lungime > other.lungime;
    }
};
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++)
        length[i] = INF;
    pq.push({1});
    while (!pq.empty()) {
        pq_elem top = pq.top();
        pq.pop();
        if (check[top.nod]) continue; // daca nodul a fost deja verificat (pentru ca avem pq), nodul are un cost mai mic deja gasit => skip
        else check[top.nod] = true; // daca nu, notam ca i-a fost gasita lungimea minima si ca a fost vizitat
        int cnt_vector = adjacency[top.nod].size();
        for (int i = 0; i < cnt_vector; i++) {
            if (top.lungime + adjacency[top.nod][i].cost < length[adjacency[top.nod][i].nodf]) {
                length[adjacency[top.nod][i].nodf] = top.lungime + adjacency[top.nod][i].cost;
                pq.push({adjacency[top.nod][i].nodf, length[adjacency[top.nod][i].nodf]});
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (length[i] == INF) length[i] = 0; // daca nu se poate ajunge la nodul i, afisam 0
        fout << length[i] << " ";
    }
    return 0;
}