C. Логистические вопросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Некоторая страна состоит из n городов, соединённых железнодорожной сетью. Транспортное сообщение страны настолько развито, что сеть состоит из минимального необходимого количества двусторонних дорог в (n - 1) дорог (иными словами, граф дорог представляет собой дерево). Из них i-я дорога, непосредственно соединяющая города ai и bi, имеет длину li километров.

Транспортную систему обслуживает государственный перевозчик ХЖД (Хорошие Железные Дороги), который, в целях упрощения ценовой политики, предлагает единственный тариф для проезда на электричке. Для того, чтобы проехать маршрут длиной t километров, требуется заплатить бурлей. При этом запрещается разбивать длинный маршрут на короткие отрезки и оплачивать их отдельно (за исполнением этого странного закона следит специальная железнодорожная полиция, ЖДП).

Большая Софтверная Компания решила организовать свой турнир по программированию. Проведя несколько отборочных туров, работники компании определили список финалистов и передали его в логистический отдел для подбора места проведения финала и решения вопроса закупки билетов. Большой Софтверной Компании не составит труда организовать финал турнира в любом из 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.

Если правильных ответов несколько, разрешается вывести любой.

Примеры
Входные данные
5
3 1 2 6 5
1 2 3
2 3 1
4 3 9
5 3 1
Выходные данные
3 192.0
Входные данные
2
5 5
1 2 2
Выходные данные
1 14.142135623730951000
Примечание

В тесте из условия оптимальный вариант выбора города для проведения финала соревнования — 3. При таком выборе стоимость проведения составит бурлей.

Во втором тесте из условия вне зависимости от выбора города потребуется заплатить за проезд пяти участникам, на каждого будет потрачено по бурлей.