아티팩트

리크와 모티는 다른 차원에서 행성의 지도를 발견했다. 지도에는 길로 연결된 $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$이면 지점 $i$에는 아티팩트가 없다. 이어지는 $n-1$개의 줄에는 세 정수 $u_i$, $v_i$, $c_i$ ($1 \leqslant u_i, v_i \leqslant n$; $1 \leqslant c_i \leqslant 10^9$)가 주어진다. 이는 지점 $u_i$와 $v_i$ 사이에 길이 $c_i$인 길이 있음을 뜻한다. 입력 그래프는 트리임이 보장된다.

$k$종류의 아티팩트를 모두 모을 수 없으면 $-1$을 출력한다. 그렇지 않으면 모든 종류의 아티팩트를 모으기 위해 리크가 걸어야 하는 최소 거리를 출력한다.

첫 번째 예제에서 최적 경로 중 하나는 $1 \to 3 \to 2 \to 3 \to 4$이다. 두 번째 예제에는 종류 5의 아티팩트가 있는 지점이 없으므로 다섯 종류를 모두 모을 수 없다. 세 번째 예제에서 최적 경로 중 하나는 $2 \to 3 \to 4$이다.