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

Петрович знает, что когда он прилетает в город под номером i, население испытывает радость A_i. А при пролёте из города i в город j Дедушка Мороз дарит радость C_ij. При этом столько же радости он дарит, пролетая из j в i. Помогите Деду Морозу Петровичу максимизировать радость, которую он может принести людям.

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

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