CF757F Team Rocket Rises Again

新年将至，Bash 想给他的朋友们送礼物。喜马拉雅地区有 $n$ 个城市，这些城市通过 $m$ 条双向道路相连。Bash 居住在城市 $s$。除了 Bash 所在的城市外，其他每座城市都有 Bash 的一位朋友。因为想带来惊喜，Bash 决定给每位朋友送一个皮卡丘。由于有些城市可能无法从 Bash 所在的城市到达，他只会给那些可以到达的城市的朋友送礼物。而且，他希望礼物能尽快送到。 他计算出了每个皮卡丘到达目的城市所需的最短时间。由于 Bash 是个完美主义者，他把每位朋友的礼物到达时间都告诉了他们。朋友们听后都非常兴奋，如果礼物延误就会感到不开心。不幸的是，火箭队得知了 Bash 的计划，并想让尽可能多的 Bash 的朋友不开心。 他们打算摧毁除 Bash 所在城市以外的其他 $n-1$ 个城市中的恰好一个。这样居住在该城市的朋友就会死亡，自然也不会开心。 注意，如果一个城市被摧毁，与之直接相连的所有道路也会被摧毁，皮卡丘可能被迫绕更远的路。 还要注意，只有那些等待礼物的朋友才算作不开心，即使他们因城市被摧毁而死亡。 既然 Bash 已经成为传奇，这次你能帮帮火箭队，计算一下通过摧毁恰好一个城市，能让 Bash 的最多多少位朋友变得不开心吗？

第一行包含三个用空格分隔的整数 $n$、$m$ 和 $s$（$2 \leq n \leq 2 \cdot 10^{5}$，$1 \leq m \leq 2 \cdot 10^{5}$，$1 \leq s \leq n$），分别表示喜马拉雅地区的城市数、道路数，以及 Bash 所在城市编号。 接下来的 $m$ 行，每行包含三个用空格分隔的整数 $u$、$v$ 和 $w$（$1 \leq u,v \leq n$，$u \neq v$，$1 \leq w \leq 10^{9}$），表示存在一条长度为 $w$ 米的道路连接城市 $u$ 和城市 $v$。 保证不存在连接同一对城市的多条道路，也不存在一条道路起终点为同一座城市。

输出一个整数，表示摧毁恰好一个城市后，最多能让 Bash 的多少位朋友变得不开心。

在第一个样例中，摧毁城市 $2$ 后，城市对 $(3,2)$ 和 $(3,4)$ 之间的最短路径长度都会发生变化，因此答案是 $2$。 由 ChatGPT 5 翻译