← 返回题目列表

Codeforces · 757/F

F. 火箭队再次崛起

中文机器翻译题面 查看原题

新年到了,Bash 想给他的朋友们送礼物。喜马拉雅地区有n个城市,它们由m条双向道路连接。 Bash住在s市。 Bash 在其他每个城市都有一位朋友。由于巴什想要给他的朋友们一个惊喜,他决定送他们每人一个皮卡丘。由于可能有一些城市无法从 Bash 的城市到达,因此他只将皮卡丘发送给那些居住在从他自己的城市可以到达的城市的朋友。他也想尽快送给他们。

他找出他的每只皮卡丘到达目的地城市的最短时间。由于他是一个完美主义者,他会告诉所有朋友他们的礼物到达的时间。皮卡丘的移动速度为每秒1米。他的朋友们听到这个消息都很兴奋,如果他们的礼物被延误了,他们会不高兴的。不幸的是,火箭队逍遥法外,他们知道了巴什的计划。他们希望最大限度地增加对 Bash 不满意的朋友的数量。

他们通过摧毁其他 n - 1 个城市之一来做到这一点。这意味着住在那个城市的朋友去世了,所以他也不高兴。

请注意,如果一座城市被摧毁,所有直接连接到该城市的道路也会被摧毁,皮卡丘可能被迫走更长的替代路线。

另请注意,只有正在等待礼物的朋友才算不快乐,即使他们死了。

既然Bash已经是一个传奇了,这次你能帮助火箭队,找出摧毁一座城市最多可以让Bash的朋友不高兴的数量吗?

输入

第一行包含三个空格分隔的整数 n、m 和 s (2 ≤ n ≤ 2·105, $${ 1 \leq m \leq \operatorname* { m i n } \left( { \frac { n ( n - 1 ) } { 2 } }, 3 \cdot 10 ^ { 5 } \right) }$$, 1 ≤ s ≤ n) — 喜马拉雅地区和 Bash 居住的城市的城市数量和道路数量。

接下来的 m 行中的每一行都包含三个空格分隔的整数 u、v 和 w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 109),表示城市 u 和城市 v 之间存在一条长度为 w 米的道路。

保证没有道路连接一个城市到其自身,并且不存在两条道路连接同一对城市。

输出

打印一个整数,即问题的答案。

示例

输入 #1

4 4 3
1 2 1
2 3 1
2 4 1
3 1 1

输出 #1

2

输入 #2

7 11 2
1 2 5
1 3 5
2 4 2
2 5 2
3 6 3
3 7 3
4 6 2
3 4 2
6 7 3
4 5 7
4 7 7

输出 #2

4

注意

在第一个样本中,在摧毁城市 2 时,城市对 (3, 2) 和 (3, 4) 之间的最短距离长度将会改变。因此答案是2。