Рознощик газет
Як і будь-який сучасний студент, що потребує додаткового заробітку, ви вирішили підробляти рознощиком газет. Вас щойно прийняли на роботу, і вам видали опис маршруту: набір адрес, зручно позначених числами від 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.