#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 50000
#define Infinit 10000000
using namespace std;

///---------FISIERE----------
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

///---------TIPURI DE DATE----------
vector < int > Graph1[Nmax];
vector < int > Graph2[Nmax];
int Vizitat[Nmax], Distanta[Nmax], Coada[Nmax];

///---------DIJKSTRA-----------
void DIJKSTRA(int n)
{
    int copie = n;
    int index;
    while( copie != 0 )
    {
        int minim = Infinit;

        for(int i = 1; i <= n; i++)
            if(!Vizitat[i] && Distanta[i] < minim)
            {
                minim = Distanta[i];
                index = i;
            }
        Vizitat[index] = 1;
        int Size = Graph1[index].size();
        for(int i = 0; i < Size; i++)
        {
            int vecin = Graph1[index][i];
            int cost = Graph2[index][i];
            if(Distanta[index] + cost < Distanta[vecin])
                Distanta[vecin] = Distanta[index] + cost;
        }
        copie --;
    }
}

int main()
{
    ///----------------CITIRE DATE DIN FISIER---------------
    int N, M, A, B, C;
    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        in >> A >> B >> C;
        Graph1[A].push_back(B);
        Graph2[A].push_back(C);
    }
    for(int i = 2; i <= N; i++)
        Distanta[i] = Infinit;

    DIJKSTRA(N);
    for(int i = 2; i <= N; i++)
    {
        if(Distanta[i] ==Infinit)
            out << "0 ";
        else
            out << Distanta[i]<< " ";
    }
    return 0;
}