Custo

É dado um grafo acíclico conexo que contém $n$ vértices e $n-1$ arestas. Cada vértice do grafo possui um valor inteiro $v_i$, representando o valor desse vértice. O somatório dos valores dos vértices do grafo é $0$. As arestas também possuem um custo $c_i$. Você deve calcular o menor custo possível para retirar $k$ arestas do grafo de modo que cada componente conexa restante também possua soma total de valores dos vértices igual a 0.

Entrada

A primeira linha da entrada contém dois inteiros $n$ e $k$, a quantidade de vértices do grafo e a quantidade de arestas a serem retiradas.

Na segunda linha há $n$ inteiros $v_i$, os valores dos vértices.

As próximas $n-1$ contém três inteiros $U_i, V_i$ e $C_i$ indicando que existe uma aresta entre os vértices $U_i$ e $V_i$.

Saída

Imprima a menor soma de custos possíveis de se remover $k$ arestas, ou imprima $-1$ caso seja impossível.

Entrada	Saida
5 1 1 1 -3 2 -1 1 2 7 1 5 2 2 3 11 2 4 8	7
8 2 7 -6 0 -1 0 -3 2 1 1 2 2 1 5 8 2 3 4 2 4 9 5 6 11 6 7 6 6 8 1	12
6 0 3 -1 -7 4 3 -1 1 2 10 2 3 13 3 5 5 2 6 6 1 4 7	-1