#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;
}