Content Delivery

You are given a computer network with $n$ nodes. The network is an undirected tree, and edge $i$ connects node $a_i$ and node $b_i$ with length $c_i$.

Every node holds one data item of its own, and the item on node $j$ has size $s_j$. A user delivers any item to any node. The delivery cost is the size of the item times the distance the item travels, and the data always follows the shortest path.

Once a delivery finishes, every node on that path, including the destination, caches the item. From the next delivery on, the item is sent by the node closest to the destination among the nodes that cache it, so the cost is the original size times the distance from that node to the destination. Nothing is cached at the start, so item $j$ sits only on node $j$.

The user chooses the item and the destination freely for every delivery. If the destination already caches the item, the distance is $0$ and the cost is $0$ as well. Find the largest total cost of $m$ deliveries.

The first line contains the number of nodes $n$ and the number of deliveries $m$. ($2 \le n \le 2000$, $1 \le m \le 10^9$)

Each of the next $n-1$ lines contains one edge as $a_i$, $b_i$, $c_i$ in this order. ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10000$)

The next line contains $n$ integers. The $j$-th integer is the size $s_j$ of the item on node $j$. ($1 \le s_j \le 10000$)

The given network is always a tree.

Print the maximum total cost of the $m$ deliveries on one line.