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

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector < pair < int, int > > v[50005];
int n, m, x, y, c;
set < pair < int , int > > s; /// retinem perechile {dist, nod} => in s.begin() avem nodul cu dist minima
int dist[50005];
int inf = 1000000000;

int main() {
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> x >> y >> c;
        v[x].push_back({y, c});
        /// pt neorientat facem si: v[y].push_back({x, c});
    }
    dist[1] = 0;
    for (int i=2;i<=n;i++) dist[i] = inf;
    s.insert({0, 1});
    while (!s.empty()) {
        int nod = s.begin()->second;
        s.erase(s.begin());
        for (auto ed: v[nod]) {
            if (dist[ed.first] > dist[nod] + ed.second) {
                s.erase({dist[ed.first], ed.first}); /// stergem nodul cu distanta veche
                dist[ed.first] = dist[nod] + ed.second; /// actualizam dist
                s.insert({dist[ed.first], ed.first}); /// il inseram din nou -> el va fi ordonat corespunzator in set
            }
        }
    }
    for (int i=2;i<=n;i++) {
        if (dist[i] == inf) g << 0 << " ";
        else g << dist[i] << " ";
    }
    return 0;
}