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

#define INFINIT 100000000

using namespace std;

typedef pair<int,int> PAIR;

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

int nrNoduri, nrMuchii, *distanta;
bool *vizitat;
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;

        myHeap.pop();

        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;

                if ( vizitat[NodCurent] ) continue;


                int cost = reprezentareGraf[NodCurent - 1][i].second;



                if( distanta[vecin] > distanta[NodCurent] + cost ){
								distanta[vecin] = distanta[NodCurent] + cost;
								myHeap.push(make_pair(-distanta[vecin],vecin)); //adaug "-distanta[vecin]" pt ca vreau min heap

                }
        }

        vizitat[NodCurent] = true;

  }

  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;
 vizitat = NULL;

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

 if ( !reprezentareGraf || !distanta || !vizitat ){
     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;

}