Breweries

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 B_i 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)*B_i, 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.

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 i^th of these lines contains the value B_i (1<=B_i<=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.

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.

1
4 2
3
4
2
7
1 2 10
2 3 21
2 4 57

42

Explanation for sample input and output:
The tree is presented in the figure below. The cities where the breweries were built are colored in yellow (the darker color).
The cost of beer transportation equal to 42 is achieved between city 3 and the brewery located in city 2.

Mugurel Ionut Andreica

Politehnica University of Bucharest Local Team Contest 2007