Description:

soda has a tree with n vertices. Each vertex has an initial color with it and the color of i-th vertex is i. And the vitalness of color i is wi. Initially, all the edges have no color and soda wants to color the edges by using the following operation:

1. choose a vertex u and a color c that vertex u contains

2. choose another vertex v and color all the edges and vertices along the shortest path from u to v with color c.

Note that one color will not cover another color, which means one edge and or vertex can have multiply colors.

After m such operations, soda computes the vitalness of the tree as follows:

1. for each color i, find the total length of edges having color i denoting as li

2. the vitalness of the tree is

Help soda find a way to make vitalness of the tree as large as possible after m such operations.

Input:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1≤n≤2000,1≤m≤10^{9}), the number of vertices and the number of operations.

The following n−1 lines describe the edges. The i-th line contains three integer ui, vi and ci (1≤ui,vi≤n,1≤ci≤10^{}^{4}) indicating that there is edge between vertex ui and vertex vi and the length is ci.

The next line contains n integers w1,w2,…,wn (1≤wi≤10^{4}), where i-th integer denotes the vitalness of i-th color.

Output:

For each case, output an integer denoting the maximum vitalness soda can get.

Sample Input:

2 3 2 1 2 1 2 3 2 1 10 100 2 100 1 2 1 1 1

Sample Output:

320 2

Source:

Submit