include <bits/stdc++.h>

using namespace std; const int maxn = 1000; const int INF = 1000000010; int n, m, s, u, v, w; bool flag[maxn] = {false};//用于标记点是否已访问过 int mp[maxn][maxn] = {0}, d[maxn]; //d[maxn]储存起点到每个点的最短路径 void Dijkstra() {

fill(d, d + maxn, INF);
d[s] = 0;
for (int i = 1 ; i <= n ; i++) {
	int u = -1, minNum = INF;
	for (int j = 1 ; j <= n ; j++) { //寻找距离起点最短距离的点
		if (flag[j] == false && d[j] < minNum) {
			u = j;
			minNum = d[j];
		}
	}
	if (u == -1)
		return;
	flag[u] = true;//标记访问的点
	for (int j = 1 ; j <= n ; j++) { //遍历与该点所有接通的路径
		if (flag[j] == false && mp[u][j] != 0 && d[u] + mp[u][j] < d[j])
			d[j] = d[u] + mp[u][j];
	}
}

}

int main() {

scanf("%d%d%d", &n, &m, &s);
for (int i = 0 ; i < m ; i++) {
	scanf("%d%d%d", &u, &v, &w);
	mp[u][v] = w;//如果是无向图则再加上mp[v][u] = w;
}
Dijkstra();
for (int i = 1 ; i <= n ; i++) {
	if (d[i] == INF) {
		printf("-1 ");
	} else {
		printf("%d ", d[i]);
	}

}
return 0;

}