#include <iostream>
using namespace std;

struct Graph {
	long long arc[105][105];
	int numVertex, numEdge;
};

void CreateGraph(Graph& G) {
	for (int i = 1; i <= G.numVertex; i++) {
		for (int j = 1; j <= G.numVertex; j++) {
			if (i == j)
				G.arc[i][j] = 0;
			else
				G.arc[i][j] = 0x7fffffff;
		}
	}
	for (int i = 0; i < G.numEdge; i++) {
		long long a, b, w;
		cin >> a >> b >> w;
		G.arc[a][b] = G.arc[b][a] = w;
	}
}

void shortest_path(Graph G, int v0) {
	long long* d = new long long[G.numVertex + 1];
	bool* tag = new bool[G.numVertex + 1];
	for (int i = 1; i <= G.numVertex; i++) {
		d[i] = G.arc[i][v0];
		tag[i] = false;
	}
	tag[v0] = true;
	int k;
	for (int i = 1; i < G.numVertex; i++) {
		long long min = 0x7fffffff;
		for (int j = 1; j <= G.numVertex; j++) {
			if (!tag[j] && d[j] < min) {
				min = d[j]; k = j;
			}
		}
		tag[k] = true;
		d[k] = min;
		for (int j = 1; j <= G.numVertex; j++) {
			if (!tag[j] && d[k] + G.arc[k][j] < d[j]) {
				d[j] = d[k] + G.arc[k][j];
			}
		}
	}
	for (int i = 1; i <= G.numVertex; i++) 
			cout << d[i] << " ";
}

int main() {
	int v0;
	Graph G;
	cin >> G.numVertex >> G.numEdge >> v0;
	CreateGraph(G);
	shortest_path(G, v0);
	return 0;
}