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