410170: GYM103967 F Артефакты

F. Артефактыограничение по времени на тест1.5 секундограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Рик и Морти обнаружили в другом измерении карту планеты, на которой изображены $$$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» (без кавычек), иначе сообщите минимальное расстояние, которое придется пройти, чтобы собрать все виды артефактов.

ПримерыВходные данные

5 4
1 3 2 4 4
1 3 1
2 3 1
3 4 1
4 5 1

Выходные данные

4

Входные данные

5 5
1 3 2 4 4
1 3 1000
2 3 5123
3 4 3341
4 5 7197

Выходные данные

-1

Входные данные

4 3
0 1 2 3
1 2 10
2 3 1
3 4 50

Выходные данные

51

Примечание

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

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

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