8612: You are given a tree...

You are given an edge-weighted tree T=(V,E) with ∣V∣=n vertices labeled through 1,2,…,n where each vertex i has a value a_i.

You need to select a subset S⊆V of at most k vertices with distinct values. You want to maximize the sum of weights of "spanned" edges, where an edge e is "spanned" if and only if there exists u,v∈S such that e lies on the only path between u and v.

The first line contains two integers n,k(1≤n≤5000,2≤k≤5), denoting the size of the tree and the maximum size of the subset you need to choose, respectively.
The second line contains n integers a₁,a₂,...,a_n(1≤a_i≤n), denoting the value of each vertex.
Then n−1 lines follow, where each line contains $3$ integers u,v,w(1≤u,v≤n,−10⁹≤w≤10⁹), denoting there is an edge (u,v) with weight w in the tree.

Output an integer in a line, denoting the maximized sum of weights of "spanned" edges.

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

6