Розносник газет#2641
Як бідний студент, перевантажений платою за навчання, ти вирішив знайти підробіток — розносити газети. Тебе найняли і видали маршрут: набір адрес, зручно пронумерованих від до .
Щоранку ти стартуєш з офісу газети (в описі маршруту він позначений адресою номер ). Треба спланувати шлях, щоб доставити газету на кожну адресу, і одразу після цього вирушити до місця навчання. На щастя, між адресами району є лише доріг, і для кожної з них відомий час, потрібний на подолання.
До того ж тобі відома інформація, як швидко можна дістатися з деяких точок до інших, у тому числі до офісу газети — наприклад, велосипедом, на скейтборді або автостопом. Який мінімальний час потрібно, щоб рознести всі газети і потрапити до місця навчання?
У першому рядку дано кількість адрес (1 \leq n \leq 100000).
У наступних n + 1 рядках записано по одному числу c_i (нумерація з i = 0, 0 \leq c_i \leq 1000000000) — час, необхідний, щоб дістатися з точки до місця навчання.
Далі подано рядків по три цілих числа , , (0 \leq a, b \leq n, a \neq b, 0 \leq c \leq 1000). Кожен з цих рядків описує дорогу між двома точками й вказує час у хвилинах, потрібний для проходження її з до .
Гарантується, що до всіх адрес можна дістатися. (Нагадаємо: офіс газети розташований у точці .)
Виведіть мінімальний час, необхідний, щоб доставити всі газети і дістатися до місця навчання.
Примітка: У цьому прикладі вигідніше відвідувати кожну адресу, повертатися до офісу й звідти прямувати до місця навчання. Наприклад, використовуючи такий маршрут: 0 \to 1 \to 0 \to 2 \to 0 \to місце навчання = 1 + 1 + 2 + 2 + 1 = 7.
Приклад 1