CF566C.Logistical Questions

Some country consists of n cities, connected by a railroad network. The transport communication of the country is so advanced that the network consists of a minimum required number of (n - 1) bidirectional roads (in the other words, the graph of roads is a tree). The i-th road that directly connects cities a__i and b__i, has the length of l__i kilometers.

The transport network is served by a state transporting company FRR (Fabulous Rail Roads). In order to simplify the price policy, it offers a single ride fare on the train. In order to follow the route of length t kilometers, you need to pay burles. Note that it is forbidden to split a long route into short segments and pay them separately (a special railroad police, or RRP, controls that the law doesn't get violated).

A Large Software Company decided to organize a programming tournament. Having conducted several online rounds, the company employees determined a list of finalists and sent it to the logistical department to find a place where to conduct finals. The Large Software Company can easily organize the tournament finals in any of the n cities of the country, so the the main factor in choosing the city for the last stage of the tournament is the total cost of buying tickets for all the finalists. We know that the i-th city of the country has w__i cup finalists living there.

Help the company employees find the city such that the total cost of travel of all the participants to it is minimum.

某国由 $n$ 座城市组成，这些城市通过铁路网相互连接。该国的交通运输极为发达，其铁路网恰好包含最少数量的 $n-1$ 条双向铁路（即铁路图构成一棵树）。第 $i$ 条铁路直接连接城市 $a_i$ 和 $b_i$，长度为 $l_i$ 千米。

该运输网络由国有运输公司 FRR（Fabulous Rail Roads）负责运营。为简化票价政策，该公司对火车旅行实行统一单程票价：若旅行路线总长为 $t$ 千米，则需支付 卢布。注意：不允许将一条长路线拆分为若干短路段并分别购票（由专门的铁路警察 RRP 监督，确保该规定不被违反）。

一家大型软件公司决定举办一场编程竞赛。在组织了若干轮线上比赛后，该公司员工已确定了一份决赛选手名单，并将其提交给后勤部门，以选定决赛举办地。该公司可在该国任意一座城市（共 $n$ 座）举办决赛，因此选择决赛城市的最主要因素是所有决赛选手前往该城市的总交通费用。已知该国第 $i$ 座城市有 $w_i$ 名杯赛决赛选手居住于此。

请帮助该公司员工找出一座城市，使得所有参赛者前往该城市的总交通费用最小。

The first line of the input contains number n (1 ≤ n ≤ 200 000) — the number of cities in the country.

The next line contains n integers _w_1, _w_2, ..., w__n (0 ≤ w__i ≤ 108) — the number of finalists living in each city of the country.

Next (n - 1) lines contain the descriptions of the railroad, the i-th line contains three integers, a__i, b__i, l__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ l__i ≤ 1000).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）—— 表示该国城市的数量。

第二行包含 $n$ 个整数 $w_1,\,w_2,\,\dots,\,w_n$（$0 \leq w_i \leq 10^8$）—— 表示居住在该国每个城市的决赛选手人数。

接下来的 $(n-1)$ 行描述了铁路网络，其中第 $i$ 行包含三个整数 $a_i,\,b_i,\,l_i$（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$，$1 \leq l_i \leq 1000$）。

Print two numbers — an integer f that is the number of the optimal city to conduct the competition, and the real number c, equal to the minimum total cost of transporting all the finalists to the competition. Your answer will be considered correct if two conditions are fulfilled at the same time:

1. The absolute or relative error of the printed number c in comparison with the cost of setting up a final in city f doesn't exceed 10 - 6;
2. Absolute or relative error of the printed number c in comparison to the answer of the jury doesn't exceed 10 - 6.

If there are multiple answers, you are allowed to print any of them.

输出两个数：一个整数 $f$，表示举办比赛的最优城市编号；以及一个实数 $c$，等于将所有决赛选手运送至该比赛城市的最小总费用。当同时满足以下两个条件时，你的答案将被视为正确：

1. 输出的数 $c$ 与在城市 $f$ 举办决赛的实际费用之间的绝对误差或相对误差不超过 $10^{-6}$；
2. 输出的数 $c$ 与裁判组标准答案之间的绝对误差或相对误差不超过 $10^{-6}$。

若存在多个可行解，你可以输出其中任意一个。

In the sample test an optimal variant of choosing a city to conduct the finals of the competition is 3. At such choice the cost of conducting is burles.

In the second sample test, whatever city you would choose, you will need to pay for the transport for five participants, so you will need to pay burles for each one of them.

在样例测试中，选择城市 3 作为比赛决赛的举办地是最优方案。此时，举办费用为 卢布。

在第二个样例测试中，无论选择哪座城市，都需要为五名参赛者支付交通费，因此需为每人支付 卢布。