J. Защищённое соединение

В стране $n$ городов. В некоторых стоят дата-центры первой компании, в некоторых — второй, в остальных ничего. Известны $m$ пар городов, которые можно соединить сегментом связи, и стоимость каждого сегмента.

Канал должен начинаться в городе с дата-центром первой компании и заканчиваться в городе с дата-центром второй. Найдите наименьшую стоимость такого канала.

Запускать Дейкстру из каждого города первой компании — до $n$ запусков и $O(nm\log n)$. Не нужно: положите в кучу сразу все города первой компании с расстоянием ноль. Это тот же многоисточниковый обход, что был в занятии по обходу в ширину, только с весами.

Формально это Дейкстра из фиктивной вершины, соединённой рёбрами нулевого веса со всеми источниками; добавлять её в граф не нужно.

Первая строка содержит числа $n$ ($2 \le n \le 5000$) и $m$ ($1 \le m \le 10^5$).

Вторая строка — $n$ чисел $a_i$ ($0 \le a_i \le 2$): $1$ — дата-центр первой компании, $2$ — второй, $0$ — ничего. Гарантируется, что есть хотя бы одна единица и хотя бы одна двойка.

Далее идут $m$ строк: два различных города и стоимость $c$ ($1 \le c \le 10^5$). Между парой городов не более одного сегмента.

Три числа $x$, $y$ и $d$ — города и наименьшая стоимость. Если пара не единственная, выведите лексикографически наименьшую по $(x, y)$.

Если соединить невозможно, выведите $-1$.