Разносчик газет
Как любой современный бедный студент, Вы решили взяться за работу с частичной занятостью, подрабатывая разносчиком газет. Вас только что приняли на работу и передали описание маршрута: набор адресов, удобно помеченных числами от 1 до n.
Каждое утро Вы начинаете в редакции газеты (которая, как оказалось, имеет в описании маршрута номер 0). Вам нужно спланировать маршрут для доставки газет по каждому указанному адресу, и кроме того Вы также хотите, чтобы добраться до места учёбы сразу после выполнения Вами работы. Вам повезло, что есть только n дорог в вашем районе обслуживаемых адресов, и для каждой них известно время, чтобы пройти по ней к месту учёбы.
Кроме того, есть данные о том, как быстро Вы можете добраться от некоторых одних пунктов до некоторых других, в том числе от редакции газеты, используя, возможно, подручные средства передвижения: езду на велосипеде, скейте или автостопом. Как быстро вы можете разнести все газеты и попасть на учёбу в учебное заведение?
Входные данные
В первой строке задано количество адресов n (1 ≤ n ≤ 100000).
В следующих n + 1 строках, содержится одно целое число c_i (нумерация начинается с i = 0, 0 ≤ c_i ≤ 1000000000) - время, которое требуется, чтобы добраться из пункта с номером i в ваше учебное заведение.
Далее содержится n строк, в каждой из которых по три целых числа a, b, c (0 ≤ a, b ≤ n, a ≠ b, 0 ≤ c ≤ 1,000). Каждая из этих строк описывает дорогу между двумя пунктами, указывая время c в минутах, чтобы пройти из a в b.
Гарантируется, что вы сможете добраться до всех адресов. (Помните, что редакция газеты расположена в пункте 0).
Выходные данные
Выведите минимальное время, которое Вам необходимо для доставки всей корреспонденции и прибытия на место учёбы.
Примечание к примеру: В этом примере лучше всего после посещения каждого адреса возвращаться в редакцию и добираться до места учёбы также оттуда оттуда. Например, по такому маршруту: 0 -> 1 -> 0 -> 2 -> 0 -> Учебное заведение = 1 + 1 + 2 + 2 + 1 = 7.