//#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 50001
#define INF 9876543

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
int	 distanta[NMAX];			// distanta de la nodul de plecare la nodul k
bool vizitat[NMAX];				// o multime in care pun elementele vizitate
int	 tata[NMAX];				// 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() {
	citire();
	//debug();
	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';
	*/
}

void init() {
	// initialez toate distantele din dist cu infinit mai putin nodul de start
	//fill(distanta.begin(), distanta.end(), -INF);
	memset(distanta, INF, sizeof(distanta));
	distanta[nodStart] = 0;
	
	// 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) {
	for(int l=0; l<Graf[nodStart].size(); l++) { 
		distanta[Graf[nodStart][l].nodVecin] = Graf[nodStart][l].dist;
		tata[Graf[nodStart][l].nodVecin] = nodStart;
	}
}

void dijkstra() {
	// nodul curent si drumul minim gasit de la nodStart la nodCurent
	int drumMinim, nodCurent = 1;
	
	// se repeta de n-1 ori
	for(int j=1; j<N; j++) {		
		// 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] &&  distanta[i] < drumMinim) {
				drumMinim = distanta[i];
				nodCurent = i;
			}
		}
		
		// am gasit nodul minim si o distanta minima 
		vizitat[nodCurent] = 1;
		
		// actualizez distantele de la nodul curent la fiecare dintre nodurile vecine daca merge
		vector<nodGraf> :: iterator k;
		for(k = Graf[nodCurent].begin(); k != Graf[nodCurent].end(); ++k) {
			if(!vizitat[k->nodVecin] && drumMinim + k->dist < distanta[k->nodVecin]) {
				distanta[k->nodVecin] = k->dist + drumMinim;
				tata[k->nodVecin] 	  = nodCurent; 
			}
		}
	}
}

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);
	}
	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<<":"<<i->dist<<", ";;
			//cout<<nod<<' '<<i->nodVecin<<' '<<i->dist<<'\n';
		cout<<'\n';
	}
	cout<<'\n';
	for(int i=1; i<=N; i++) {
		for(int l=0; l<Graf[i].size(); l++) { 
			cout<<"Dist de la "<<i<<" la "<<Graf[i][l].nodVecin<<" este "<<Graf[i][l].dist<<'\n';
		}
	}*/
}