ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1463. Радость населению!

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Каждый Дедушка Мороз хочет удивить своими подарками ребятишек. В этом году Дед Мороз Петрович хочет удивить ребят дальнего Закукуевска. Петрович уверен, что для того, чтобы произвести настоящее впечатление, надо выбрать маршрут без повторяющихся городов. Чтобы как можно больше обрадовать местное население, он хочет проехать по самым людным местам. Петрович взял карту городов Закукуевска и соединил некоторые пары городов, где люди будут ждать его. Между не соединёнными парами городов Дед Мороз Петрович решил не летать. При этом получилось, что если из города i Петрович может долететь до города j, то существует ровно один маршрут такого полёта. В начале путешествия Петрович может прилететь в любой город.
Петрович знает, что когда он прилетает в город под номером i, население испытывает радость Ai. А при пролёте из города i в город j Дедушка Мороз дарит радость Cij. При этом столько же радости он дарит, пролетая из j в i. Помогите Деду Морозу Петровичу максимизировать радость, которую он может принести людям.

Исходные данные

В первой строке число N (1 ≤ N ≤ 50000) городов в Закукуевске и число K пар городов на карте, которые соединил Петрович. Во второй строке раположены числа Ai (i = 1..N); Ai ≤ 10000. Далее следует K строк, в каждой по 3 числа a, b, c, означающие, что при пролёте из a в b Петрович приносит c радости (ab; c ≤ 10000). Все числа — целые и неотрицательные.

Результат

В первой строке выведите максимальное количество испытанной населением Закукуевска радости, во второй строке — длину оптимального маршрута L. В третьей — наилучший маршрут Деда Мороза Петровича (L чисел через пробел). Если ответов несколько, выведите любой.

Примеры

исходные данныерезультат
2 1
1 1
1 2 1
3
2
1 2
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
37
4
5 4 2 3
Автор задачи: Александр Торопов, особая благодарность Александру Ипатову
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2006