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.
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≤109), 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≤104) 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≤104), where i-th integer denotes the vitalness of i-th color.
For each case, output an integer denoting the maximum vitalness soda can get.
2 3 2 1 2 1 2 3 2 1 10 100 2 100 1 2 1 1 1