#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <utility>
#include <queue>
#include <set>

#define INFINIT 100000000

using namespace std;

typedef pair<int,int> PAIR;

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

int nrNoduri, nrMuchii, *distanta;
vector <PAIR> *reprezentareGraf;
priority_queue <PAIR> myHeap; //va fi un min Heap

void Dijkstra(int NodStart){

	for(int i = 1 ; i <= nrNoduri; i ++ )
                            distanta[i] = INFINIT;

	distanta[NodStart] = 0;

	myHeap.push(make_pair(0,NodStart));

	while (!myHeap.empty()){

        int NodCurent = myHeap.top().second;
        int costNodCurent = -myHeap.top().first; // extrag cu "-" pt ca am introdus cu "-" --> vreau min heap

        myHeap.pop();

        if ( distanta[NodCurent] != costNodCurent )
                                                continue;

        int lim = reprezentareGraf[NodCurent - 1].size();

        for(int i = 0; i < lim; i++){ //parcurg vecinii nodului curent ( cel cu cost minim gasit anterior )

                int vecin = reprezentareGraf[NodCurent - 1][i].first;
                int costVecin = reprezentareGraf[NodCurent - 1][i].second;

                if( distanta[vecin] > costNodCurent + costVecin ){

                        distanta[vecin] = costNodCurent + costVecin;
                        myHeap.push(make_pair(-distanta[vecin],vecin)); //adaug "-distanta[vecin]" pt ca vreau min heap

                }
        }

  }

  for (int i = 2; i <= nrNoduri; i++)
	 if ( distanta[i] == INFINIT )
                        fout<< 0 <<" ";
     else
            fout<<distanta[i]<<" ";

}

int main(){

    if ( !fin ){
        cout << "\nEroare la deschiderea fisierului !\n";
        exit(-1);
    }

 fin >> nrNoduri;

 reprezentareGraf = NULL;
 distanta = NULL;

 reprezentareGraf = new vector < pair<int,int> >[nrNoduri + 5];
 distanta = new int[nrNoduri + 5];

 if ( !reprezentareGraf || !distanta ){
     cout << "\nEroare la alocarea dinamica !\n";
     exit(-1);
 }

 fin >> nrMuchii;

 for (int i = 1; i <= nrMuchii; i++) {

    int x , y , cost;

    fin >> x >> y >> cost;

    reprezentareGraf[x-1].push_back(make_pair(y,cost));

 }

 Dijkstra(1);

    return 0;

}