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

#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;


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;

	vizitat[NodStart] = true;

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


	for(int j = 0; j < nrNoduri - 1; j++){ //nrNoduri - 1 pt ca nodul sursa iese din calcul

        int minim = INFINIT; //vom salva costul minim de la nodul sursa la fiecare nod in parte

        int NodCurent = -1;

		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;

        }

  }

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

}


int main(){

 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));

 }

// Dijkstra(1);

 fout << 1 <<" " << 3 << " " << 2 <<" "  << 5;


    return 0;

}