CF757F.Team Rocket Rises Again

It's the turn of the year, so Bash wants to send presents to his friends. There are n cities in the Himalayan region and they are connected by m bidirectional roads. Bash is living in city s. Bash has exactly one friend in each of the other cities. Since Bash wants to surprise his friends, he decides to send a Pikachu to each of them. Since there may be some cities which are not reachable from Bash's city, he only sends a Pikachu to those friends who live in a city reachable from his own city. He also wants to send it to them as soon as possible.

He finds out the minimum time for each of his Pikachus to reach its destination city. Since he is a perfectionist, he informs all his friends with the time their gift will reach them. A Pikachu travels at a speed of 1 meters per second. His friends were excited to hear this and would be unhappy if their presents got delayed. Unfortunately Team Rocket is on the loose and they came to know of Bash's plan. They want to maximize the number of friends who are unhappy with Bash.

They do this by destroying exactly one of the other n - 1 cities. This implies that the friend residing in that city dies, so he is unhappy as well.

Note that if a city is destroyed, all the roads directly connected to the city are also destroyed and the Pikachu may be forced to take a longer alternate route.

Please also note that only friends that are waiting for a gift count as unhappy, even if they die.

Since Bash is already a legend, can you help Team Rocket this time and find out the maximum number of Bash's friends who can be made unhappy by destroying exactly one city.

又到了一年之交，巴什（Bash）想给他的朋友们送礼物。喜马拉雅地区共有 $n$ 座城市，它们由 $m$ 条双向道路连接。巴什住在城市 $s$。除他所在的城市外，其余每座城市中恰好有一位他的朋友。由于巴什希望给朋友们一个惊喜，他决定向每位朋友寄送一只皮卡丘（Pikachu）。由于可能存在某些城市无法从巴什所在的城市到达，因此他仅向那些居住在可从其所在城市到达的城市中的朋友寄送皮卡丘，并且希望尽可能快地送达。

他计算出每只皮卡丘抵达各自目的地城市的最短时间。由于他是个完美主义者，他将每位朋友的礼物预计到达时间全部告知了他们。皮卡丘的移动速度为每秒 1 米。朋友们听到这个消息后非常兴奋；但如果他们的礼物迟到，他们便会感到不开心。不幸的是，火箭队（Team Rocket）正在四处活动，他们得知了巴什的计划，企图最大化对巴什感到不开心的朋友人数。

他们通过恰好摧毁其余 $n-1$ 座城市中的一座来实现这一目标。这意味着居住在该城市的那位朋友将死亡，因此他也会感到不开心。

注意：若某座城市被摧毁，则所有与该城市直接相连的道路也将同时被摧毁，皮卡丘可能被迫选择一条更长的替代路径。

还需注意：只有那些正在等待礼物的朋友才被计入“不开心”的人数中，即使他们因城市被毁而死亡。

巴什早已是传奇人物，那么这一次，你能帮助火箭队，找出通过恰好摧毁一座城市所能造成的最多不开心的朋友人数吗？

The first line contains three space separated integers n, m and s (2 ≤ n ≤ 2·105, , 1 ≤ s ≤ n) — the number of cities and the number of roads in the Himalayan region and the city Bash lives in.

Each of the next m lines contain three space-separated integers u, v and w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 109) denoting that there exists a road between city u and city v of length w meters.

It is guaranteed that no road connects a city to itself and there are no two roads that connect the same pair of cities.

第一行包含三个用空格分隔的整数 $n$、$m$ 和 $s$（$2 ≤ n ≤ 2·10^5$，，$1 ≤ s ≤ n$）——分别表示喜马拉雅地区城市的数量、道路的数量，以及 Bash 所居住的城市编号。

接下来的 $m$ 行中，每行包含三个用空格分隔的整数 $u$、$v$ 和 $w$（$1 ≤ u, v ≤ n$，$u ≠ v$，$1 ≤ w ≤ 10^9$），表示城市 $u$ 与城市 $v$ 之间存在一条长度为 $w$ 米的道路。

保证不存在连接同一城市的道路，且不存在两条道路连接相同的两个城市。

Print a single integer, the answer to the problem.

输出一个整数，即该问题的答案。

In the first sample, on destroying the city 2, the length of shortest distance between pairs of cities (3, 2) and (3, 4) will change. Hence the answer is 2.

在第一个样例中，摧毁城市 2 后，城市对 (3, 2) 和 (3, 4) 之间的最短距离长度将发生变化。因此答案为 2。