Козак Вус нарешті знайшов країну своєї мрії. Вона складається з n міст, між якими не проходить жодна дорога. Звичайно, Вус захотів виправити цю ситуацію, і тому придумав m різних двосторонніх доріг, які можна було би прокласти. За його задумом кожна дорога з'єднує два різні міста. Але виникла проблема: кожне місто i може виділити на побудову доріг ci копійок, а для кожної дороги j на її побудову пішло б wj копійок. Тому Козак вирішив, що йому вистачить побудувати декілька доріг так, аби всі міста стали сусідами. Міста називаються сусідами, якщо можливо дорогами країни дістатися з одного міста в інше.
При плануванні своїх робіт Козак Вус зрозумів одну річ: коли він будуватиме чергову дорогу, міста будуть об'єднуватися в групи сусідів. Щоб побудувати j-ту дорогу, потрібно, щоб міста (або їх сусіди), між якими будується дорога, сумарно мали принаймні wj копійок (адже спершу потрібно заплатити за дорогу й лише потім будувати). Після побудови дороги бюджети міст об'єднуються, а вартість дороги вираховується з нової спільної казни.
Для кожного з n міст ви знаєте число ci — кількість копійок, які може витратити місто i. Для кожної з m доріг ви знаєте числа vi, ui та wi, які означають, що дорога i з'єднує міста vi та ui, а на її побудову потрібно wi копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати.
Перший рядок містить три цілі числа n, m та g (1≤n≤106, 0≤m≤106, 0≤g≤7) — кількість міст, кількість доріг та номер блока відповідно.
Наступний рядок містить n цілих чисел c1,c2,…,cn (1≤ci≤106) — початкова кількість копійок в i-му місті.
Кожний із наступних m рядків містить по три цілі числа vi, ui та wi (1≤vi,ui≤n, 1≤wi≤106) — номер міст, між якими i-та дорога, та ціна її побудови відповідно.
Для того, щоб показати дороги, які потрібно побудувати, використовуйте таку функцію:
Ця функція будує дорогу під номером i (1≤i≤m).
Вам потрібно реалізувати одну функцію:
n — кількість міст у країні;
m — кількість доріг, які можна прокласти;
g — номер блока;
ci (∣c∣=n) — початкова кількість копійок у i-тому місті;
vi та ui (∣v∣=∣u∣=m) — номери вершин, що з'єднує i-та дорога;
wi (∣w∣=m) "— кількість копійок, необхідних на побудування i-тої дороги;
ця функція повинна повертати true
, якщо можливо правильно вибрати послідовність доріг, і false
, якщо ні.
Якщо ваша функція повертає true
, то до того, як вона його поверне, вона має зробити виклики функції add
для всіх побудованих доріг у тому порядку, у якому вони побудуються.
Якщо функція повертає false
, то в першому рядку буде виведено одне число −1.
Інакше в першому рядку буде виведено число q — кількість побудованих доріг. У наступних q рядках буде виведено по одному число x — номер побудованої дороги.
У першому прикладі країна складається з 4-ох міст, а план Козака Вуса складається з 5-и доріг. Спочатку будується дорога під номером 4: міста 2 та 4 об'єднаються у групу, а з їхнього загального бюджету сплачується 3 копійки. На рахунку цієї групи залишається 6 копійок. Після побудови дороги під номером 2 бюджет групи буде складати 4 копійки, адже приєдналося місто 3 з бюджетом у 2 копійки, а також витратили 4 копійки на побудову дороги. Після побудови 3-ої дороги всі міста стануть сусідами, а їх загального бюджету вистачить, щоб заплатити 5 копійок за дорогу.
У другому прикладі неможливо вибрати дороги та порядок їх побудови так, щоб усі міста стали сусідами й щоб за усі дороги було заплачено.
(3 балів) n≤10; m=n−1; ci=1; wi=1; якщо побудувати всі m доріг, усі міста стануть сусідами;
(8 балів) n,m≤10;
(12 балів) n,m≤105; ci=1;
(14 балів) n,m≤105; усі wi однакові;
(16 балів) n,m≤103;
(19 балів) n,m≤105;
(12 балів) n,m≤5⋅105;
(16 балів) без додаткових обмежень.