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

#define INFINIT 100000000
#define MAX 500005

using namespace std;

typedef pair<int,int> PAIR;

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

int nrNoduri, nrMuchii, distanta[MAX];
bool vizitat[MAX];
vector <PAIR> reprezentareGraf[MAX];


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].size();

	for (int i = 0; i < lim; i++ ) //distanta initiala de la NodStart la celelalte
        distanta[reprezentareGraf[NodStart][i].first] = reprezentareGraf[NodStart][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].size();

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

                int vecin = reprezentareGraf[NodCurent][i].first;

                if( !vizitat[vecin] && distanta[vecin] > distanta[NodCurent] + reprezentareGraf[NodCurent][i].second )
								distanta[vecin] = distanta[NodCurent] +reprezentareGraf[NodCurent][i].second;

        }

  }

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

}


int main(){

 fin >> nrNoduri >> nrMuchii;

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

    int x , y , cost;

    fin >> x >> y >> cost;

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

 }

 Dijkstra(1);

    return 0;

}