Problems
Злі корови
Злі корови
Останніми роками спостерігається швидке поширення 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 балів): без додаткових обмежень.
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