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

#define NMAX 100
#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];
vector<int> row(NMAX, INF);
vector< vector<int> > Graf(NMAX, row);
//int Graf[100][100];

// 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() {
	// aloc zone de memorie pt structurii dijkstra
	//distanta.reserve(N+1);
	//tata.reserve(N+1);
	//memset(Graf, INF, sizeof(Graf));
		
	citire();
	init();
	//debug();
	
	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);
	distanta[nodStart] = 0;
	
	// umplu vectorul tata cu -1 - o valoare necunoscuta
	//tata[nodStart] = 0;
	
	// adaug in multimea nodurilor vizitate nodul de inceput
	vizitat[nodStart] = true;

	//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;
	}*/
	
	for(int i=1; i<=N; i++) {
		distanta[i] = Graf[nodStart][i];
		tata[i]		= 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;
			}
		}
		//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 
			
			if(!vizitat[i] && distanta[i] > drumMinim + Graf[nodCurent][i]) {
				// in nodul i vin din nodul curent
				tata[i] = nodCurent;
				// am gasit o distanta minima
				distanta[i] = drumMinim + Graf[nodCurent][i];
			}
		}
	}
}

void citire() {
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	int a, b, c;
	
	vector<int> aux;
	
	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;
		
		//aux.push_back(c);
		
		// salvez nodul in array
		//Graf[a].push_back(tmp);
		
		Graf[a][b] = c;
	}
	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';
		}
	}*/
}