include

include

define IFN 0x3f3f3f3f

using namespace std; int n, m, s; int g[1000][1000]; int vis[1000]; int dis[1000]; int path[1000];

void dijkstra() {

dis[s] = 0;
int v;
for (int i = 0; i < n; i++) {
	int min = IFN;
	for (int j = 1; j <= n; j++) {
		if (vis[j] == 0 && dis[j] < min) {
			v = j;
			min = dis[j];
		}
	}

	vis[v] = 1;
	for (int j = 1; j <= n; j++) {
		if (vis[j] == 0 && dis[j] > dis[v] + g[v][j] && g[v][j] != 0) {
			dis[j] = dis[v] + g[v][j];
			path[j] = v;
		}
	}
}

}

int main() {

memset(g, 0, sizeof(g));
memset(vis, 0, sizeof(vis));
memset(dis, IFN, sizeof(dis));
memset(path, 0, sizeof(path));
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
	int u, v, w;
	cin >> u >> v >> w;
	g[u][v] = w;
}
dijkstra();
for (int i = 1; i <= n; i++) {
	if (dis[i] != IFN) {
		cout << dis[i] << " ";
	} else {
		cout << "-1" << " ";
	}

}
return 0;

}