#include <iostream>
#include <fstream>
#include <vector>
#include <set>

#define NMAX 50001
#define INF 999999

using namespace std;

// noduri si muchii
int N, M;

/*
	@ In graf valorile sunt tinute asa Graf[1] = lista de adiacenta a nodului 1
	@ fiecare element din lista aia e de tipul nodGraf => Graf[1][2].dist = distanta dintre nodul 1 si
	@ elementul care se alfa pe pozitia 2 in lista de adiacenta a nodului 1
*/
// trebuie sa stochez si nodul vecin si distanta dintre ele
struct nodGraf {
	int nodVecin;
	int dist;
} tmp;
// declar un vector de tipul nodGraf
vector<nodGraf> Graf[NMAX];

// structuri de date pt Dijkstra
vector<int> distanta(NMAX, INF);		// distanta de la nodul de plecare la nodul k
bool	 	vizitat[NMAX];	// o multime in care pun elementele vizitate
vector<int>	tata(NMAX, -11);			// in nodul p vin din nodul tata[p]

// iteratori
vector<int> :: iterator it;

// nodul de start
int nodStart = 1;

// functii locale
void citire();
void debug();
void init();
void dijkstra();

int main() {
	// aloc zone de memorie pt structurii dijkstra
	//distanta.reserve(N+1);
	//tata.reserve(N+1);
	
	citire();
	
	init();
	dijkstra();
	
	ofstream fout("dijkstra.out");
	for(int i=2; i<=N; i++) {
		fout<<distanta[i]<<' ';
	}
	fout.close();
	
	/*
	for(int i=2; i<=N; i++) {
		cout<<"Distanta minima de la "<<nodStart<<" la "<<i<<" este "<<distanta[i]<<'\n';
	}
	cout<<'\n';
	for(int i=1; i<=N; i++)
		cout<<distanta[i]<<" ";
	cout<<'\n';
	for(int i=1; i<=N; i++)
		cout<<tata[i]<<" ";
	cout<<'\n';
	//debug();*/
}

void init() {
	// initialez toate distantele din dist cu infinit mai putin nodul de start
	//fill(distanta.begin(), distanta.end(), -INF);
	distanta[nodStart] = 0;
	
	// umplu vectorul tata cu -1 - o valoare necunoscuta
	//fill(tata.begin(), tata.end(), -1);
	
	// adaug in multimea nodurilor vizitate nodul de inceput
	vizitat[nodStart] = true;
	
	// pun primele distante - noduri ale lui nodStart
	vector<nodGraf> :: iterator k;
	for(k = Graf[nodStart].begin(); k != Graf[nodStart].end(); ++k) {
		distanta[k->nodVecin] = k->dist;
	}
}

void dijkstra() {
	// nodul curent si drumul minim gasit de la nodStart la nodCurent
	int drumMinim, nodCurent;
	
	// se repeta de n-1 ori
	for(int i=1; i<N; i++) {
		// pp ca cel mai scurt drum e infinit
		drumMinim = INF;
		// caut cea mai mica distanta a unui nod nevizitat
		for(int i=1; i<=N; i++) {
			// daca nodul nu e vizitat si distanta e minima
			if(!vizitat[i] && drumMinim  > distanta[i]) {
				drumMinim = distanta[i];
				nodCurent = i;
			}
		}
		//cout<<drumMinim<<" "<<nodCurent<<" | ";
		
		// am gasit nodul minim si o distanta minima 
		vizitat[nodCurent] = true;
		
		// actualizez distantele de la nodul curent la fiecare dintre nodurile vecine daca merge
		for(int i=1; i<=N; i++) {
			// daca nodul pe care il actualizez nu e vizitat
			// si daca am gasit o distanta mai mica 
			
			// folosesc iteratori - caut 
			vector<nodGraf> :: iterator k;
			int distantaCurenta;
			//k = find(Graf[nodCurent].begin(), Graf[nodCurent].end(), i);
			
			// caut iteratorul 
			for(k = Graf[nodCurent].begin(); k != Graf[nodCurent].end(); ++k) {
				if(k->nodVecin == i)
					distantaCurenta = k->dist;
			}

			//cout<<p->nodVecin<<' ';
			if(!vizitat[i] && distanta[i] > drumMinim + distantaCurenta) {
				// in nodul i vin din nodul curent
				tata[i] = nodCurent;
				// am gasit o distanta minima
				distanta[i] = drumMinim + distantaCurenta;
			}
		}
	}
}

void citire() {
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	int a, b, c;
	for(int i=1; i<=M; i++) {
		fin>>a>>b>>c;
		// graful e orientat
		
		// salvez nodul vecin
		tmp.nodVecin = b;
		
		// salvez distanta de la a la nodul vecin
		tmp.dist = c;
		
		// salvez nodul in array
		Graf[a].push_back(tmp);
		
		distanta[i] = INF;
		tata[i] = 1;
	}
	fin.close();
}

void debug() {
	// itearator
	vector<nodGraf>::iterator i;
	for(int nod = 1; nod <= N; nod++) {
		cout<<nod<<"->";
		for(i = Graf[nod].begin(); i != Graf[nod].end(); ++i)
			cout<<i->nodVecin<<", ";
			//cout<<nod<<' '<<i->nodVecin<<' '<<i->dist<<'\n';
		cout<<'\n';
	}
}