#include <bits/stdc++.h>
using namespace std;
const int nmax=5e4+5;
int n, m, sol[nmax];
vector<pair<int,int>> L[nmax];

void dijkstra (){ // functia djkstra
    priority_queue <pair<int,int>> q; // declaram codita:) de tip {- best_distance from source to node, node}
    q.push({0,1}); // push la nodul 1 (sursa) cu distanta 0
    while (!q.empty()){ // cat timp nu am parcurs toate nodurile / mai avem noduri in coada
        int node = q.top().second, dist = -q.top().first; // ne retinem aici frumusel in node efectiv nodul si in dist
        // minut distanta. De ce cu minus? pai in priority queue (by default) numerele sunt ordonate descrescator.
        // Noi vrem sa parcurgem distantele cele mai mici primele pt ele au sansele cele mai mare de a ne da solutia optima.
        q.pop(); // aici eliminam din coada nodul pe care tocmai l-am verificat
        if (dist > sol[node]) continue; // Daca gasim apoi o solutie mai lunga decat ce avem deja, nu mai intram in forul ala de jos :)
        for (auto son : L[node]) // pentru fiecare fiu de-al lui node (son e de tip pair<int,int> adica <fiu de al lui node, distanta de la node la fiu
            if ((sol[son.first] == 0) || (sol[node] + son.second < sol[son.first])){ // daca nu am gasit solutie pentru fiu SAU daca
            // (cel mai bun drum de la sursa la node + distanta de la node la son ) este mai mica decat (solutia pe care am gasit o pana acum pt fiu
                sol[son.first] = son.second + sol[node]; // atunci efectiv schimbam solutia cu ce am gasit
                q.push({-sol[son.first],son.first}); // si apoi foarte imp, dam push la {- distanta, fiu}. am zis ca punem cu - ca sa fie in ordinea buna
            }
    }
}
int main()
{
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");
    f >> n >> m;
    while (m--){
        int x, y, d;
        f >> x >> y >> d;
        L[x].push_back({y,d});
    }
    sol[1] = 0;
    dijkstra();
    for (int i = 2; i <= n; ++i) g << sol[i] << " ";
    return 0;
}