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

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

const int NMAX = 50001;
const int MMAX = 250001;
const int INF = (NMAX - 1) * 20001;
struct muchie {
    int nod, cost;
};
int N, M;
vector<vector<muchie> > G(NMAX);

void citire() {
    fin >> N >> M;
    int x, y, c;
    for (int i = 0; i < M; i++) {
        fin >> x >> y >> c;
        muchie m;
        m.nod = y - 1;
        m.cost = c;
        G[x - 1].push_back(m);
    }
}

void Dijkstra() {
    vector<int> viz(N, 0);
    vector<int> d(N);

    for (int i = 0; i < N; i++)
        d[i] = INF;
    d[0] = 0;
    for (int i = 0; i < N; i++) {
        int index = -1 , min = INF;
        for (int j = 0; j < N; j++)
            if (d[j] < min && !viz[j]) {
                min = d[j];
                index = j;
            }
        if(index == -1) break;
        for (auto edge:G[index])
            if (d[index] + edge.cost < d[edge.nod])
                d[edge.nod] = d[index] + edge.cost;
        viz[index] = 1;
    }
    for (int i = 1; i < N; i++)
        if(d[i]!=INF) fout << d[i] << " ";
        else cout<<0<<" ";
}

void Dijkstra2() {
    set<pair<int, int>> S;
    vector<int> d(N, INF);
    d[0] = 0;
    S.insert(make_pair(0, 0));
    while(!S.empty()){
        int index = (*S.begin()).second;
        for (auto edge:G[index])
            if (d[index] + edge.cost < d[edge.nod]) {
                S.erase(make_pair(d[edge.nod], edge.nod));
                d[edge.nod] = d[index] + edge.cost;
                S.insert(make_pair(d[edge.nod], edge.nod));
            }
        S.erase(S.begin());
    }
    for (int i = 1; i < N; i++)
        if (d[i] == INF) fout << 0 << " ";
        else fout << d[i] << " ";
}

int main() {
    citire();
    Dijkstra2();

    return 0;
}