#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, *predecesor;
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 ++ ){ //initializare vectori

		vizitat[i] = false; //marcam toate nodurile ca fiind nevizitate

        distanta[i] = INFINIT;

	}

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

	for (int i = 0; i < lim; i++ ){ //distanta initiala de la NodStart la celelalte
        distanta[reprezentareGraf[NodStart - 1][i].first] = reprezentareGraf[NodStart - 1][i].second;

        //in heap adaug perechea de forma ( cost , muchie ) ... adaug cu "-cost" pt ca vreau min heap , iar cand scot inmultesc cu -1
        myHeap.push(make_pair(-reprezentareGraf[NodStart - 1][i].second,reprezentareGraf[NodStart - 1][i].first));
	}

	vizitat[NodStart] = true;

	distanta[NodStart] = 0; //costul de la nodul sursa la nodul sursa va fi implicit 0

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

	while (!myHeap.empty()){ //nrNoduri - 1 pt ca nodul sursa iese din calcul

        int minim = myHeap.top().first * (-1); //vom salva costul minim de la nodul sursa la fiecare nod in parte

        int NodCurent = myHeap.top().second;

	/*	for(int vecin = 1; vecin <= nrNoduri; vecin++)  //aflu costul minim de la nodul sursa la nodul i

			if( !vizitat[vecin] && distanta[vecin] < minim ){

									minim = distanta[vecin];

									NodCurent = vecin; //salvam nodul cu costul minim
			}
*/


        vizitat[NodCurent] = true;

        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[vecin] && distanta[vecin] > distanta[NodCurent] + reprezentareGraf[NodCurent - 1][i].second )
								distanta[vecin] = distanta[NodCurent] +reprezentareGraf[NodCurent - 1][i].second;

        }

        myHeap.pop();

  }

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

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

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

 }


/*
  for (int i = 0; i < nrNoduri; i++) {

    int lim = reprezentareGraf[i].size();

    cout << i + 1 << " : ";

    for ( int j = 0; j < lim; j++)
        cout << reprezentareGraf[i][j].first << " " << reprezentareGraf[i][j].second << " || " ;

    cout << endl;
 }
*/

 Dijkstra(1);


    return 0;

}