28525번 - Артефакты 다국어

Рик и Морти обнаружили в другом измерении карту планеты, на которой изображены $n$ пунктов раскопок, соединенных тропинками. Тропинка с номером $i$ соединяет пункты с номерами $u_i$ и $v_i$ и имеет длину $c_i$.

Разумеется, Рик сразу заметил, что количество тропинок равняется в точности $n - 1$, и из любого пункта можно добраться до любого другого. Иными словами, структура дорог и пунктов представляет из себя дерево, но для Морти это определение слишком сложное, поэтому Рик оставил Морти изучать теорию графов, а сам отправился исследовать это измерение.

Инопланетный информатор сообщил ему, что всего существует $k$ видов артефактов, и в пункте номер $i$ хранится артефакт вида $a_i$. Так очень удачно совпало, что у Рика очередное соревнование с одним из известных расхитителей космических гробниц, и для победы Рику нужно собрать все $k$ различных видов артефактов.

Одной из проблем является то, что внутри этого измерения не работают никакие продвинутые технологии. Поэтому Рик может заранее создать порталы в запланированных стартовом и конечном пункте маршрута, а вот остальной маршрут придется пройти пешком. Чтобы сэкономить свое время, Рик хочет заранее выбрать стартовый пункт, конечный пункт и сам путь (не обязательно простой) так, чтобы пройденное им расстояние было минимальным, и при этом на пути он бы собрал все различные виды артефактов.

Рик, конечно, и сам может справиться с поиском такого кратчашего пути, но, может быть, у вас есть время заняться этим, пока он собирает всю необходимую для путешествия экипировку?

В первой строке через пробел даны два целых числа $n$ и $k$ ($2 \leqslant n \leqslant 10^5$; $1 \leqslant k \leqslant 6$) --- количество пунктов и необходимое количество артефактов.

В следующей строке через пробел даны $n$ целых чисел $a_i$ --- виды артефактов в каждом пункте ($0 \leqslant a_i \leqslant k$). В случае, если $a_i = 0$, считается, что в вершине не хранится никакой из видов артефактов.

В следующих $n - 1$ строках даны тройки целых чисел $u_i$, $v_i$, $c_i$, обозначающие наличие тропинки длины $c_i$ между пунктами $u_i$ и $v_i$ ($1 \leqslant u_i, v_i \leqslant n$; $1 \leqslant c_i \leqslant 10^9$). Гарантируется, что структура графа представляет из себя дерево.

В случае, если невозможно собрать $k$ различных видов артефактов, выведите <<-1>> (без кавычек), иначе сообщите минимальное расстояние, которое придется пройти, чтобы собрать все виды артефактов.

В первом примере одним из оптимальных путей будет $1 \to 3 \to 2 \to 3 \to 4$.

В втором примере у нас нет пункта, в котором находится артефакт под номером $5$, а значит невозможно собрать все пять артефактов.

В третьем примере одним из оптимальных путей будет $2 \to 3 \to 4$.