Deal

Problem 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 $w_i$. 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:
3. for each color $i$, find the total length of edges having color $i$ denoting as $l_i$
4. the vitalness of the tree is $\displaystyle \sum_{i=1}^{n}l_i \cdot c_i$ 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 \le n \le 2000, 1 \le m \le 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 $u_i$, $v_i$ and $c_i$ $(1 \le u_i, v_i \le n, 1 \le c_i \le 10^4)$ indicating that there is edge between vertex $u_i$ and vertex $v_i$ and the length is $c_i$. The next line contains $n$ integers $w_1, w_2, \dots, w_n$ $(1 \le w_i \le 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

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6