#include <bits/stdc++.h>
#include <iostream>

using namespace std;

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


vector<pair<int,int>>adiacenta[50000];//liste de perechi pt noduri pe adiacenta[i] vom avea perechea(j,cost) astfel incat exista muchie de la i la j cu costul cost
int n,m;//noduri, muchii
int total = 0;
vector <int> parinte;//vector in care constuiesc drumul minim
priority_queue< pair<int,int>, vector <pair<int,int>>, greater<pair<int,int>> > pq; //coada de prioritati pt aflarea muchiei cu cost minim cu un nod in arbore si unul in afara
vector <int>distanta;//distanta[i] = distanta de la nodul de start la i


void Dijkstra(int i)
{

    pq.push(make_pair(0, i));//inseram in coada de prioritati nodul de start, are costul 0 initial
    distanta[i] = 0;


    int varf;
    while (!pq.empty())
    {
        varf = pq.top().second; //luam varful cu costul del mai mic (coada prioritizeaza dupa primul element, adica costul)



        pq.pop();

        for (pair<int,int> e : adiacenta[varf])//parcurgem vecinii nodului scos din coada
        {
            int vecin = e.first; //val vecinilui
            int c = e.second;//costu muhciei de la nodul scos la vecin

            if (distanta[vecin] > distanta[varf] + c)//daca exista un drum mai scurt la vecin prin varful extras
            {

                // Updatez distanta pana la vecin
                distanta[vecin] = distanta[varf] + c;
                pq.push(make_pair(distanta[vecin], vecin));
                parinte[vecin] = varf;



            }

        }


    }


}



int main()
{
    ///Dijkstra e asemanator cu alg lui Prim, cu diferenta ca atunci cand scoatem un nod din coada
    ///si ii pargurgem vecinii vecinii verificam daca exista un drum mai mic  la vecinul nevizitat prin nodul extras
    ///decat drumul deja determinat(<=> relaxarea muchiilor)

    in>>n>>m;
    int x,y,c;


    for(int i = 0; i<m ; i++)
    {
        in>>x>>y>>c;

        adiacenta[x-1].push_back(make_pair(y-1, c)); //graf orientat
    }



    distanta.assign(n,10000);
    parinte.assign(n,-1);
    Dijkstra(0);

    //verific care punct de control e mai apropiat de s

    for(int i = 1; i <n; i++)
    {
        if(distanta[i] == 10000)
            out<<"0 ";

        else
            out<<distanta[i]<<" ";


    }

    return 0;
}