某个国家由 n 个城市组成,通过铁路网络连接。该国的交通通讯非常先进,以至于网络由所需的最少数量(n - 1)条双向道路组成(换句话说,道路图是一棵树)。直接连接ai 和bi 城市的第i 条道路长度为li 公里。
运输网络由国有运输公司 FRR(Fabulous Rail Roads)提供服务。为了简化价格政策,它提供火车单程票价。为了走完t公里长的路线,你需要支付$$t^{\frac{3}{2}}$$ burles。请注意,禁止将长路线分成短段并分别支付费用(特别铁路警察(RRP)负责控制,以确保不违反法律)。
一家大型软件公司决定组织一场编程锦标赛。经过多轮线上比赛,公司员工确定了决赛名单,并发送给后勤部门寻找决赛地点。大型软件公司可以轻松地在全国n个城市中的任何一个举办比赛决赛,因此选择最后阶段比赛城市的主要因素是所有决赛选手购买门票的总费用。我们知道该国第 i 个城市有 wi 杯决赛入围者居住在那里。
帮助公司员工找到城市,使得所有参与者前往该城市的总出行费用最小。
输入
输入的第一行包含数字 n (1 ≤ n ≤ 200 000) — 该国城市的数量。
下一行包含 n 个整数 w1, w2, ..., wn (0 ≤ wi ≤ 108) — 居住在该国每个城市的决赛入围者的数量。
接下来 (n - 1) 行包含铁路的描述,第 i 行包含三个整数 ai, bi, li (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ li ≤ 1000)。
输出
打印两个数字——一个整数f是进行比赛的最佳城市的编号,另一个是实数c,等于运送所有决赛选手参加比赛的最低总成本。如果同时满足两个条件,您的答案将被视为正确:
1、打印的数字c与在f城市设立决赛的成本相比的绝对或相对误差不超过10 - 6;
2. 印刷数字c与陪审团答案相比的绝对或相对误差不超过10 - 6。
如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
5 3 1 2 6 5 1 2 3 2 3 1 4 3 9 5 3 1
输出 #1
3 192.0
输入 #2
2 5 5 1 2 2
输出 #2
1 14.142135623730951000
注意
在样本测试中,选择城市进行决赛的最佳变体是 3。在这种选择下,进行决赛的成本为 $$3 \cdot 4 ^ { \frac { 3 } { 2 } } + 1 \cdot 1 ^ { \frac { 3 } { 2 } } + 2 \cdot 0 ^ { \frac { 3 } { 2 } } + 6 \cdot 9 ^ { \frac { 3 } { 2 } } + 5 \cdot 1 ^ { \frac { 3 } { 2 } } = 192$$ 布尔。
在第二个样本测试中,无论您选择哪个城市,您都需要支付 5 名参与者的交通费,因此您需要为每一位参与者支付 $$2\sqrt{2}$$ burles。