#include <stdio.h>
#include <limits.h>
#define inf 0x3f3f3f3f
const int maxn = 10001;
int  n, dist[maxn], map[maxn][maxn], pre[maxn], s;
//s为起点,dist[i]表示i到起点的最短距离，map记录图信息，pre记录前驱，原点，终点
void Dijkstra() {
	int min = INT_MAX;//导入limits.h
	int k;
	bool p[maxn];
	for (int i = 1; i <= n; i++) {//初始化map
		p[i] = false;
		if (i != s) {
			dist[i] = map[s][i];
			pre[i] = s;
		}
	}
	dist[s] = 0;
	p[s] = true;
	for (int i = 1; i <= n - 1; i++) {
		k = 0;
		for (int j = 1; j <= n; j++) {
			if (!p[j] && dist[j] < min) {
				min = dist[j];
				k = j;
			}
		}
		if (k == 0) {
			return;
		}
		p[k] = true;
		for (int j = 1; j <= n; j++) {
			if (!p[j] && map[k][j] != INT_MAX && dist[j] > dist[k] + map[k][j]) {
				dist[j] = dist[k] + map[k][j];
				pre[j] = k;
			}
		}
	}
}

int main() {
	int m;//m条路线
	while (true) {
		scanf("%d %d %d", &n, &m, &s);
		if (n == 0)
			break;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					map[i][j] = 0;
				} else {
					map[i][j] = inf;
				}
			}
		}
		for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			scanf("%d", &map[x][y]);
			map[y][x] = map[x][y];
		}
		Dijkstra();
		for (int i = 1; i <= n; i++) {
			printf("%d", dist[i]);
			printf("\n");
		}
	}
	return 0;
}