#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMax = 50000 + 2, oo = 2000000000;
int N, M, D[NMax];
bool S[NMax];
vector <pair <int, int> > G[NMax];

void Citire (){
    in >> N >> M;
    int x, y, k;
    for (int i = 1; i <= M; i++){
        in >> x >> y >> k;
        G[x].push_back(make_pair(y, k));
    }
}

void Dijkstra(){
    for (int i = 2; i <= N; i++)
        D[i] = oo;
    for (int k = 1; k < N; k++){
        int Min = oo, Nod, Cost;
        for (int j = 1; j <= N; j++)
            if (D[j] < Min && S[j] == 0){
                Min = D[j];
                Nod = j;
            }
        S[Nod] = 1;
        for (int i = 0; i < (int)G[Nod].size(); i++){
            int Vecin = G[Nod][i].first;
            Cost = G[Nod][i].second;
            D[Vecin] = min(D[Vecin], D[Nod] + Cost);
        }
    }
}

void Afisare (){
    for (int i = 2; i <= N; i++){
        if (D[i] == oo)
            out << "0 ";
        else
            out << D[i] << " ";
    }
}

int main (){
    Citire();
    Dijkstra();
    Afisare();
    return 0;
}