本题没有可用的提交语言。

题目描述

某城市现有若干消防站。部分居民抱怨其住所离最近消防站的距离过远，因此需新建一个消防站。你的任务是选择新消防站的位置，以最小化这些不满居民住所到最近消防站的最大距离。

城市布局

• 城市最多有 $500$ 个路口（编号为 $1$ 至$i$），由不同长度的道路段连接。
• 每个路口最多连接 $20$ 条道路段。
• 房屋和消防站的位置均视为位于路口（忽略路口到实际建筑物的距离）。
• 每个路口至少有一户居民。
• 同一路口可存在多个消防站。

输入格式

• 第一行：两个正整数 $f$（现有消防站数量，$f \leq 100$）和 $i$（路口数量，$i \leq 500$）。
• 接下来 $f$ 行：每行一个整数，表示现有消防站所在的路口编号。
• 后续若干行：每行三个正整数，表示两个不同路口及其连接道路段的长度。所有道路均为双向通行，且任意两个路口之间均存在通路。

输出格式

输出一个整数，表示应新建消防站的路口编号（若有多个最优解，选择编号最小的），使得所有路口到最近消防站的最大距离最小化。

输入样例 1

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

输出样例 1

5

来源
Waterloo local 1999.09.25