Problem Description
People drink a lot of beer in Romania. For each city i of the N cities of the country (numbered from 1 to N), the amount of beer Bi demanded by its inhabitants is known. In order to satisfy the overall demand, a famous beer company wishes to build K breweries in K distinct cities of Romania. From these breweries, beer will be transported to other cities using the existing road network. Each road connects two distinct cities and has a certain length. Because of the recent floods, the road network of Romania has the shape of a tree: that is, there is exactly one path between any pair of cities. Let’s condier a city i and a brewery located in a city X, which is the closest brewery to i. The cost of transporting beer to the city i is dist(i,X)*Bi, where dist(i,X) is the distance between city i and city X. The beer company wants to choose the locations of the K breweries in such a way that the maximum cost of transporting beer to any city in the country is minimized.
Input
The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 2 integer numbers: N (1<=N<=100.000) and K (1<=K<=N). The next N lines contain the beer demands of each city: the ith of these lines contains the value Bi (1<=Bi<=10.000). The next N-1 lines contain 3 integers each: A, B and L (1<=L<=10.000), meaning that there exists a road of length L between city A and city B.
Output
For each of the T test cases, in the order given in the input, print one line containing the minimum value for the maximum cost of transporting beer, in the case of an optimal placement of the breweries.
Sample Input
1
4 2
3
4
2
7
1 2 10
2 3 21
2 4 57
Sample Output
42
