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

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

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

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

    int 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()
{
    int i;
    for(i = 1; i < N; i++) distanta[i] = oo;

    de_vizitat.push(0);
    int 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();

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

    return 0;
}