#include <iostream>
#include <set>
#include <vector>
#include <fstream>

using namespace std;

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

const int NMAX = 50005;
const int inf = 0x3f3f3f3f;

vector <pair <int, int>> G[NMAX];
set <pair <int, int>> s;

int dist[NMAX];

int n, m;
void init(int nodes){
    for (int i = 1; i < nodes + 2; ++i) {
        dist[i] = inf;
    }
}

void citire(){
    in >> n >> m;
    init (n);
    dist[1] = 0;

    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        in >> x >> y >> cost;
        G[x].emplace_back (make_pair (y, cost));
    }

}

void dijkstra(){
    s.insert (make_pair (0, 1));

    while(!s.empty ()){
        int nod = s.begin () -> second;
        s.erase (s.begin ());

        for (int i = 0; i < G[nod].size (); ++i) {
            int vec = G[nod][i].first;
            int costVec = G[nod][i].second;

            if(dist[vec] > dist[nod] + costVec){
                s.erase ({dist[vec], vec});
                dist[vec] = dist[nod] + costVec;
                s.insert ({dist[vec], vec});
            }
        }
    }
}
void afisare(){
    for (int i = 2; i <= n; ++i) {
        if(dist[i] == inf)
            out << "0 ";
        else
            out << dist[i] << " ";
    }
}

int main() {

    citire();
    dijkstra();
    afisare();

    return 0;
}