Козак Вус і найкраща країна

Козак Вус нарешті знайшов країну своєї мрії. Вона складається з $n$ міст, між якими не проходить жодна дорога. Звичайно, Вус захотів виправити цю ситуацію, і тому придумав $m$ різних двосторонніх доріг, які можна було би прокласти. За його задумом кожна дорога з'єднує два різні міста. Але виникла проблема: кожне місто $i$ може виділити на побудову доріг $c_i$ копійок, а для кожної дороги $j$ на її побудову пішло б $w_j$ копійок. Тому Козак вирішив, що йому вистачить побудувати декілька доріг так, аби всі міста стали сусідами. Міста називаються сусідами, якщо можливо дорогами країни дістатися з одного міста в інше.

При плануванні своїх робіт Козак Вус зрозумів одну річ: коли він будуватиме чергову дорогу, міста будуть об'єднуватися в групи сусідів. Щоб побудувати $j$-ту дорогу, потрібно, щоб міста (або їх сусіди), між якими будується дорога, сумарно мали принаймні $w_j$ копійок (адже спершу потрібно заплатити за дорогу й лише потім будувати). Після побудови дороги бюджети міст об'єднуються, а вартість дороги вираховується з нової спільної казни.

Для кожного з $n$ міст ви знаєте число $c_i$ — кількість копійок, які може витратити місто $i$. Для кожної з $m$ доріг ви знаєте числа $v_i$, $u_i$ та $w_i$, які означають, що дорога $i$ з'єднує міста $v_i$ та $u_i$, а на її побудову потрібно $w_i$ копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати.

Вхідні дані

Перший рядок містить три цілі числа $n$, $m$ та $g$ ($1\le n\le 10^6$, $0\le m\le 10^6$, $0\le g\le 7$) — кількість міст, кількість доріг та номер блока відповідно.

Наступний рядок містить $n$ цілих чисел $c_1,c_2,\dots ,c_n$ ($1\le c_i\le 10^6$) — початкова кількість копійок в $i$-му місті.

Кожний із наступних $m$ рядків містить по три цілі числа $v_i$, $u_i$ та $w_i$ ($1\le v_i,u_i\le n$, $1\le w_i\le 10^6$) — номер міст, між якими $i$-та дорога, та ціна її побудови відповідно.

Протокол взаємодії

Для того, щоб показати дороги, які потрібно побудувати, використовуйте таку функцію:

void add(integer i)

• Ця функція будує дорогу під номером $i$ ($1\le i\le m$).

Вам потрібно реалізувати одну функцію:

boolean solve(integer n, integer m, integer g, array of integers c, array of integers v,
              array of integers u, array of integers w)

• $n$ — кількість міст у країні;

• $m$ — кількість доріг, які можна прокласти;

• $g$ — номер блока;

• $c_i$ ($|c|=n$) — початкова кількість копійок у $i$-тому місті;

• $v_i$ та $u_i$ ($|v|=|u|=m$) — номери вершин, що з'єднує $i$-та дорога;

• $w_i$ ($|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$ копійок за дорогу.

У другому прикладі неможливо вибрати дороги та порядок їх побудови так, щоб усі міста стали сусідами й щоб за усі дороги було заплачено.

Оцінювання

1. ($3$ балів) $n\le 10$; $m=n-1$; $c_i=1$; $w_i=1$; якщо побудувати всі $m$ доріг, усі міста стануть сусідами;

2. ($8$ балів) $n,m\le 10$;

3. ($12$ балів) $n,m\le 10^5$; $c_i=1$;

4. ($14$ балів) $n,m\le 10^5$; усі $w_i$ однакові;

5. ($16$ балів) $n,m\le 10^3$;

6. ($19$ балів) $n,m\le 10^5$;

7. ($12$ балів) $n,m\le 5\cdot 10^5$;

8. ($16$ балів) без додаткових обмежень.