#include <iostream.h>
#include <fstream.h>

/**
	@Drumuri de cost minim in graf
	Programul: drum de cost minim in graf orientat
*/

#define INF 1002 // infinit 
#define NMaxVf 3000
int N, X0; // n - nr noduri, x0 - nodul de inceput
int pre[NMaxVf], M[NMaxVf]; // pre[i] = j, in nodul i ajung din nodul j; M = multimea varfurilor alese
double C[NMaxVf][NMaxVf]; // matricea costurilor
double d[NMaxVf]; // d[x] =  costul drumului de cost minim de la X0 la x

void init(); // citire si initializare matrice C, M, d, pre
void dijkstra(); // genereaza drumul de cost minim
void afisare(); // afiseaza drumul de cost minim

int main() {
	init();
	dijkstra();
	afisare();
}

void init() {
	int m, x, y; // m = nr de muchii; x,y - valori temporare
	double c; // cost temporar;
	// deschid fisierul
	ifstream fin("dijkstra.in");
	// citesc prima linie
	fin>>N>>m>>X0;
	// umplu matricea costurilor cu INFinit
	// daca nu ar exista drum de la i la j, atunci C[i][j] = INF
	for(int i=1; i<=N; i++)
		for(int j=i+1; j<=N; j++)
			C[i][j] = C[j][i] = INF;
	// citesc legaturile
	for(int i=1; i<=m; i++) {
		fin>>x>>y>>c;
		C[x][y] = c;
	}
	// initializez d[] si pre[]
	for(int i=1; i<=N; i++) {
		// lungimile drumurilor din X0 la nodurile veine
		d[i] = C[X0][i];
		// initial pp ca din nodul X0 ajung in orice nod
		pre[i] = X0;
	}
	// in multimea nodurile alese primul nod e X0
	M[X0]   = 1;
	// in nodul X0 nu ajung de nicaieri - cu el incep
	pre[X0] = 0;
	// inchid fisierul
	fin.close();
}

void dijkstra() {
	int VfMin; // retin nodul din care plec in altele
	double dMin; // drumul de cost minim curent
	for(int j=1; j<N; j++) {
		// presupunem ca cel mai scurt drum e INF
		dMin = INF; 
		for(int i=1; i<=N; i++)
			// se determina un varf neselectat din graf care nu apratine M cu cel mai mic cost
			if(!M[i] && d[i] < dMin) {
				// am gasit un posibil nod 
				dMin = d[i];
				VfMin = i;
			}
		// il pun in multime
		M[VfMin] = 1;
		for(int i=1; i<=N; i++)
			// actualizez distantele catre celelalte noduri
			if(!M[i] && d[i] > dMin + C[VfMin][i]) {
				// nodul din care am ajuns in nodul i
				pre[i] = VfMin;
				// distanta noua
				d[i] = dMin + C[VfMin][i];
			}
	}
}

void afisare() {
	// in d[i] va fi costul drumului minim de la X0 la nodul i
	ofstream fout("dijkstra.out");
	int lg, dr[NMaxVf];
	for(int i=1; i<=N; i++)
		if(i != X0) {
			fout<<d[i]<<" ";
			/*cout<<"\nCostul drumului de cost minim de la "<<X0<<" la "<<i<<" este "<<d[i]<<'\n';
			cout<<"Drumul  de cost minim este: ";
			dr[0] = i, lg = 0;
			while(pre[dr[lg]]) {
				dr[++lg] = pre[dr[lg-1]]; 
			}
			for(int j=lg; j>=0; j--)
				cout<<dr[j]<<" ";
			cout<<'\n';*/
		}
}