#include <stdio.h>
#include <limits.h>
#define INF UINT_MAX
int main () {
int i, j; // Переменные бщего назначения
int n, m, temp1, temp2, temp3, start; // Для ввода данных
int minWeight, idMinWeight; // Для алгоритма
int graph[100][100];
int valid[100];
int weight[100];
/* Ввод данных */
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = INF;
}
valid[i] = 1;
weight[i] = INF;
}
for (i = 0; i < m; i++) {
scanf("%d %d %d", &temp1, &temp2, &temp3);
graph[temp1][temp2] = temp3;
graph[temp2][temp1] = temp3;
}
scanf("%d", &start);
/* Алгоритм */
weight[start] = 0;
for (i = 0; i < n; i++) {
minWeight = INF + 1;
idMinWeight = -1;
for (j = 0; j < n; j++) {
if (valid[j] && weight[j] < minWeight) {
minWeight = weight[j];
idMinWeight = j;
}
}
for (j = 0; j < n; j++) {
if ((weight[idMinWeight] + graph[idMinWeight][j]) < weight[j]) {
weight[j] = weight[idMinWeight] + graph[idMinWeight][j];
}
}
valid[idMinWeight] = 0;
}
for (i = 0; i < n; i++) {
printf("%d ", weight[i]);
}
printf("\n");
return 0;
}
