J. Стоимость до каждого дата-центра

Как классная задача J, но выведите наименьшую стоимость канала до каждого города второй компании — в порядке возрастания номеров городов.

Многоисточниковая Дейкстра из всех городов первой компании даёт это сразу: искомое — просто расстояния до нужных вершин. Второй проход с номерами источников здесь не нужен вовсе.

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

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

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

В первой строке — количество городов второй компании.

Во второй — для каждого из них по возрастанию номера наименьшая стоимость канала или $-1$.