Злі корови

Останніми роками спостерігається швидке поширення Extremely Green Oxen Illness (EGOI) — хвороба, що робить корів небезпечними для туристів. Після кількох інцидентів було вирішено, що ми маємо відокремити райони, де пасуться корови від районів, де ходять туристи.

У вас є карта Альп. На карті є $n$ районів. Кожен з районів може бути або населений коровами, або туристичним, або пустим. Деякі пари цих районів з'єднані двонаправленими дорогами. Кожна дорога має невід'ємну довжину. (Мовою теорії графів, карта це неорієнтовний граф з зваженими ребрами.)

Ви можете побудувати стіни в деяких районах. Як тільки Ви будуєте стіну в районі, цей район стає недоступним для корів та туристів — вони більше не зможуть проходити через цей район.

Ваше завдання — вибрати набір районів, де будуть побудовані стіни. Цей набір районів має задовольняти наступні умови:

• Він має складатись лише з пустих районів.

• Він має відокремлювати райони з коровами від туристичних. Отже, корови не повинні мати можливість пройти по дорогах до туристичного району (без проходження через райони з стінами).

• Він не має відокремлювати туристичні райони один від одного. Отже, туристи повинні мати можливість пройти по дорогах від будь-якого туристичного району до будь-якого іншого туристичного району (без проходження через райони з стінами).

Якщо є декілька варіантів, як досягти описаної вище мети, ми будемо хвилюватись лише про простоту обслуговування стін. Стіни будуть утримуватись спеціальними бригадами. Існує рівно одна така бригада в кожному з туристичних районів.

Для будь-якого району $A$ ми визначаємо його віддаленість як мінімальну довжину шляху між $A$ та деяким туристичним районом. (Довжина шляху це сума довжин доріг. Зверніть увагу, що шлях може проходити через стіни та райони з коровами — бригада, що обслуговує стіну, має усі можливості та знаряддя, щоб здійснити такий рух.)

Віддаленість набору районів це максимальна віддаленість будь-якого району в цьому наборі.

Серед усіх наборів районів з стінами, що задовольняють усі наведені умови, знайдіть та поверніть набір з найменшою можливою віддаленістю. Якщо існує декілька таких наборів, поверніть будь-який з них.

Зверніть увагу, що кількість вибраних районів не грає ролі. Тобто, не обов'язково використовувати мінімальну кількість стін.

Giriş verilənləri

Перший рядок містить два цілі числа $n$ та $m$ ($2\le n\le 3\cdot 10^5$, $n-1\le m\le 3\cdot 10^5$) — кількість районів та доріг відповідно. Райони пронумеровані від $1$ до $n$.

Другий рядок містить $n$ цілих чисел $t_1,...,t_n$, де $t_i$ рівне $-1$, якщо $i$-й район населений коровами, $0$, якщо пустий, та $1$, якщо це туристичний район.

Останні $m$ рядків описують дороги. $j$-й з них містить три цілі числа $a_j$, $b_j$ та ${\ell }_j$ ($1\le a_j<b_j\le n$, $0\le {\ell }_j\le 10^9$), що позначають дорогу між районами $a_j$ та $b_j$ довжини ${\ell }_j$.

Гарантується, що:

• між будь-якими двома районами є не більше однієї дороги,

• в даний момент можливо пройти між будь-якими двома районами, використовуючи 0 або більше доріг,

• існує щонайменше один район, населений коровами,

• існує щонайменше один туристичний район.

Çıxış verilənləri

Якщо неможливо побудувати стіни, як вказано в умові, виведіть -1.

Інакше, перший рядок має містити число $k$ — кількість доріг, які Ви хочете побудувати. Другий рядок має містити $k$ цілих чисел — номери районів, де Ви хочете побудувати стіни. (Ці номери мають бути різними числами від $1$ до $n$, включно. Вони не обов'язково мають бути в певному порядку.)

Ваш вивід буде прийнятий, якщо набір підходить під умови та він з мінімальною віддаленістю.

Nümunələr

Qeyd

В усіх прикладах, блакитний колір використовується для туристичних районів, коричневий для районів, населених коровами, та оранжевий для стін.

У першому прикладі, мінімальна можлива віддаленість рівна 2, що досягається розміщенням доріг в райони $4$, $5$ та $6$. Зверніть увагу, що ми не можемо розмістити стіни в районах $4$, $2$ та $6$, навіть отримуючи віддаленість $1$, бо тоді буде неможливо пройти між туристичними районами $1$ та $3$ без проходження через стіни.

У другому прикладі, віддаленість району 2 рівна 1000, віддаленість району 3 рівна 30, оскільки це може бути досягнуто по шляху 1–5–4–3. (Нагадуємо, що бригади можуть проходити через стіни та районів з коровами). Отже, ми маємо розмістити стіни в районах 5 та 3 (не 2), і тоді віддаленість буде рівна 30.

Qiymətləndirmə

Блок 1 (7 балів): $n\le 10$.

Блок 2 (22 бали): усі довжини ${\ell }_j=0$.

Блок 3 (16 балів): існує рівно один туристичний район.

Блок 4 (11 балів): існує рівно $n-1$ доріг (мовою теорії графів, заданий граф є деревом).

Блок 5 (8 балів): ми маємо $n,m\le 2000$ та усі довжини ${\ell }_j=1$.

Блок 6 (36 балів): без додаткових обмежень.