配点: 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 。
作者: 蓟 长度由