eolymp
Competitions

European Girls' Olympiad in Informatics 2021, II Day

Злі корови

Останніми роками спостерігається швидке поширення Extremely Green Oxen Illness (EGOI) --- хвороба, що робить корів небезпечними для туристів. Після кількох інцидентів було вирішено, що ми маємо відокремити райони, де пасуться корови від районів, де ходять туристи. У вас є карта Альп. На карті є $n$ районів. Кожен з районів може бути або населений коровами, або туристичним, або пустим. Деякі пари цих районів з'єднані двонаправленими дорогами. Кожна дорога має невід'ємну довжину. (Мовою теорії графів, карта це неорієнтовний граф з зваженими ребрами.) Ви можете побудувати стіни в деяких районах. Як тільки Ви будуєте стіну в районі, цей район стає недоступним для корів та туристів --- вони більше не зможуть проходити через цей район. Ваше завдання --- вибрати набір районів, де будуть побудовані стіни. Цей набір районів має задовольняти наступні умови: \begin{itemize} \item Він має складатись лише з пустих районів. \item Він має відокремлювати райони з коровами від туристичних. Отже, корови не повинні мати можливість пройти по дорогах до туристичного району (без проходження через райони з стінами). \item Він \emph{не} має відокремлювати туристичні райони один від одного. Отже, туристи повинні мати можливість пройти по дорогах від будь-якого туристичного району до будь-якого іншого туристичного району (без проходження через райони з стінами). \end{itemize} Якщо є декілька варіантів, як досягти описаної вище мети, ми будемо хвилюватись лише про простоту обслуговування стін. Стіни будуть утримуватись спеціальними бригадами. Існує рівно одна така бригада в кожному з туристичних районів. Для будь-якого району $A$ ми визначаємо його \emph{віддаленість} як мінімальну довжину шляху між $A$ та деяким туристичним районом. (Довжина шляху це сума довжин доріг. Зверніть увагу, що шлях \textbf{може} проходити через стіни та райони з коровами --- бригада, що обслуговує стіну, має усі можливості та знаряддя, щоб здійснити такий рух.) \emph{Віддаленість} набору районів це \textbf{максимальна} віддаленість будь-якого району в цьому наборі. Серед усіх наборів районів з стінами, що задовольняють усі наведені умови, знайдіть та поверніть набір з \textbf{найменшою можливою} віддаленістю. Якщо існує декілька таких наборів, поверніть будь-який з них. Зверніть увагу, що кількість вибраних районів не грає ролі. Тобто, \textbf{не} обов'язково використовувати мінімальну кількість стін. \InputFile Перший рядок містить два цілі числа $n$ та $m$ ($2 \leq n \leq 3 \cdot 10^5$, $n-1 \leq m \leq 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$. Гарантується, що: \begin{itemize} \item між будь-якими двома районами є не більше однієї дороги, \item в даний момент можливо пройти між будь-якими двома районами, використовуючи 0 або більше доріг, \item існує щонайменше один район, населений коровами, \item існує щонайменше один туристичний район. \end{itemize} \OutputFile Якщо неможливо побудувати стіни, як вказано в умові, виведіть \texttt{-1}. Інакше, перший рядок має містити число $k$ --- кількість доріг, які Ви хочете побудувати. Другий рядок має містити $k$ цілих чисел --- номери районів, де Ви хочете побудувати стіни. (Ці номери мають бути різними числами від $1$ до $n$, включно. Вони не обов'язково мають бути в певному порядку.) Ваш вивід буде прийнятий, якщо набір підходить під умови та він з мінімальною віддаленістю. \Note В усіх прикладах, блакитний колір використовується для туристичних районів, коричневий для районів, населених коровами, та оранжевий для стін. \includegraphics[scale=0.7]{https://static.e-olymp.com/content/d8/d8b122ff052d4f8ab7d4fbf420c80fc7.png} У першому прикладі, мінімальна можлива віддаленість рівна 2, що досягається розміщенням доріг в райони $4$, $5$ та $6$. Зверніть увагу, що ми не можемо розмістити стіни в районах $4$, $2$ та $6$, навіть отримуючи віддаленість $1$, бо тоді буде неможливо пройти між туристичними районами $1$ та $3$ без проходження через стіни. \includegraphics[scale=0.7]{https://static.e-olymp.com/content/c3/c3fc070219ae4273b2053bc3e71e4021.png} У другому прикладі, віддаленість району 2 рівна 1000, віддаленість району 3 рівна 30, оскільки це може бути досягнуто по шляху 1--5--4--3. (Нагадуємо, що бригади можуть проходити через стіни та районів з коровами). Отже, ми маємо розмістити стіни в районах 5 та 3 (не 2), і тоді віддаленість буде рівна 30. \Scoring Блок 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 балів): без додаткових обмежень.
Time limit 6 seconds
Memory limit 256 MiB
Input example #1
10 14
1 0 1 0 0 0 0 0 -1 -1
1 2 1
1 6 1
2 3 1
2 5 2
3 4 1
4 5 1
4 8 2
5 6 1
5 7 1
6 7 2
6 10 1
7 8 1
7 9 1
8 9 1
Output example #1
3
4 5 6 
Input example #2
5 5
1 0 0 -1 0
1 2 1000
2 3 1000
3 4 10
4 5 10
1 5 10
Output example #2
2
3 5 
Input example #3
4 3
1 0 -1 1
1 2 0
2 3 21
2 4 13
Output example #3
-1
Author Anton Tsypko