#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define oo 1000000
using namespace std;

struct nod{
    unsigned long long y, d;
};
vector<nod> graf[50001];
queue<unsigned long long> de_vizitat;
unsigned long long distanta[50001];
unsigned long long N, M;

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

void citeste_fa()
{
    f >> N >> M;

    unsigned long long i, x;
    nod n;
    for(i = 0; i < M; i++){
        f >> x >> n.y >> n.d;
        x--, n.y--;
        graf[x].push_back(n);
    }
}

void aplica_dijkstra_fa()
{
    unsigned long long i;
    for(i = 1; i < N; i++) distanta[i] = oo;

    de_vizitat.push(0);
    unsigned long long x, y, d;
    while(!de_vizitat.empty()){

        x = de_vizitat.front();
        de_vizitat.pop();

        for(i = 0; i < graf[x].size(); i++){

            y = graf[x][i].y;
            d = graf[x][i].d + distanta[x];
            if(distanta[y] > d){

                distanta[y] = d;
                de_vizitat.push(y);
            }
        }
    }
}

int main()
{
    citeste_fa();

    aplica_dijkstra_fa();

    unsigned long long i;
    for(i = 1; i < N; i++)
        if(distanta[i] != oo) g << distanta[i] << ' ';
        else g << "0 ";
    g << '\n';

    return 0;
}