Artifacts

Rick and Morty found a map of a planet in another dimension. The map shows $n$ dig sites connected by paths. Path $i$ connects sites $u_i$ and $v_i$ and has length $c_i$. There are exactly $n-1$ paths, and every site can reach every other site, so the structure is a tree. An alien informant reported that there are $k$ kinds of artifacts in total, and site $i$ holds an artifact of kind $a_i$. Rick is in a competition with a known tomb raider and must collect all $k$ kinds. Advanced technology does not work in this dimension. Rick can create portals at the start and end points of the route in advance, but he must walk the rest of the route. He chooses the start point, the end point, and the route (not necessarily simple) so that the distance he walks is minimal, and the route collects all kinds of artifacts.

The first line contains two integers $n$ and $k$ ($2 \leqslant n \leqslant 10^5$; $1 \leqslant k \leqslant 6$), separated by a space. They are the number of sites and the number of required artifact kinds. The next line contains $n$ integers $a_i$ ($0 \leqslant a_i \leqslant k$), the artifact kind at each site. If $a_i = 0$, site $i$ holds no artifact. The next $n-1$ lines each contain three integers $u_i$, $v_i$, $c_i$ ($1 \leqslant u_i, v_i \leqslant n$; $1 \leqslant c_i \leqslant 10^9$). This means a path of length $c_i$ connects sites $u_i$ and $v_i$. The input graph is guaranteed to be a tree.

If it is impossible to collect all $k$ kinds of artifacts, print $-1$. Otherwise, print the minimum distance Rick must walk to collect all kinds of artifacts.

In the first example, one optimal route is $1 \to 3 \to 2 \to 3 \to 4$. In the second example, no site holds artifact kind 5, so it is impossible to collect all five kinds. In the third example, one optimal route is $2 \to 3 \to 4$.