odd doctor 已更新


Time Limit
Memory Limit
Judge Program

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 (1n2000,1m109), the number of vertices and the number of operations.
The following n1 lines describe the edges. The i-th line contains three integer ui, vi and ci (1ui,vin,1ci104) 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 (1wi104), where i-th integer denotes the vitalness of i-th color.


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

Sample Input:
3 2
1 2 1
2 3 2
1 10 100
2 100
1 2 1
1 1
Sample Output:

2015 Multi-University Training Contest 6