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