← 返回题目列表

AtCoder · tkppc4_2_e

E. 蛰居族

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

配点: 400 点

問題文

阳光明媚的日子里,塔普利斯和从天使学校毕业的天使们 1 卡拉天使 N 最多 装满了 N 人类天使降临下界!于是,我决定跟随前辈天马同学的脚步,成为一名闭关者!
然而,天使们意识到再这样下去他们将无法见面,所以他们决定走长途巴士路线,以便可以去彼此的房间。 L 我决定获得一张免费车票,这样我就可以免费乘坐以下路线。
下面的总线是 M 有路线,i 第二条路线是天使 A_i 藏身的房间和天使 B_i 连接两个方向上锁的房间,路线长度为 C_i 。
天使都是孤独的,所以每个天使 q 如果你不能遇到一个超越人类的天使,你就会因为孤独而从天堂坠落。
因此,塔普里斯创造了一些东西来帮助天使应对他们的孤独。 对于q,必须购买免费巴士票的路线的最大长度, 我试图找到L 的最小值,但这很困难,所以我决定问你。
你的工作是Q查询,每个给出 关于 q_i ,所有的天使包括我自己 q_i 比人类更需要遇见天使 就是找到L (L \geq 0)。
请注意,天使不能使用免费机票以外的任何其他方式旅行。

制約

  • 所有输入均为整数
  • 2 \leq N, M, Q \leq 10^5
  • 1 \leq A_i, B_i \leq N
  • 0 \leq C_i \leq 10^{10}
  • 1 \leq q_i \leq 10^5
  • 给定的图不一定是简单的或连通的。


入力

输入是按以下格式从标准输入给出的。 请输出

N M Q
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_{M-1} B_{M-1} C_{M-1}
A_M B_M C_M
q_1
q_2
⋮
q_{Q-1}
q_Q

出力

Q 行。 请在
i 第几行包含,i 最小值 请输出 L 的值。
什么样的 如果设置 L 的值后仍无法满足条件,则作为此查询的答案 trumpet 。


入力例1

9 10 4
1 2 3
1 4 1
3 4 4
2 3 1
4 5 9
5 6 3
6 7 4
7 8 2
8 9 3
6 9 5
2
3
5
10

出力例1

3
4
9
trumpet

例如,1 对于第二个问题,包括我自己在内的所有天使 2 你必须遇到的不仅仅是人。
在此示例中,L = 2 和 就 L = 3 而言,可以使用免费车票的巴士如下图所示。


在此图中,L = 2 如果天使 5, 6, 9 包括我自己 1 你只能遇见人类天使。
L = 3 说到天使 1 是一个天使{1, 2, 3, 4} 和天使 您可以与 5 是一个天使{5, 6} 和天使 您可以与 7 是一个天使{7, 8, 9}见面。这样,所有的天使,包括我自己, 2 你能遇到的天使比人类还多。
因此,q_1 = 2 的答案是 3 。


作者: 蓟 长度由