A famous travel and tourism company succeed to win a new discount coupon, The coupon is only allowed to be used in the Treeland. In case you haven't heard about Treeland yet, Treeland is a city that has $$$n$$$ tourist places, the roads between these tourist places are specific which means you can move from a tourist place to another if and only if there is a road between them, Every road has a cost $$$w_i$$$ and you have to pay $$$w_i$$$ $$$sp$$$ for traveling using the $$$i-th$$$ road, there are $$$n - 1$$$ road between all tourist places in total and it's guaranteed that you can go from any tourist place to any other tourist place throughout a finite sequence of roads, that is, the $$$n$$$ tourist places form a weighted connected tree.

The discount coupon can be used as follows: The travel and tourism company can choose a set $$$S$$$ of $$$k$$$ tourist places, and for every road $$$i$$$ that lies on the shortest path between two nodes $$$u$$$ and $$$v$$$ such that $$$u \in S$$$ and $$$v \in S$$$, the company can travel using this road for free for one month.

The company has a schedule of $$$m$$$ trips for the next month and it wants to use the coupon to achieve the biggest discount, asking you to choose the set $$$S$$$ optimally for them.

The trip starts at some node $$$u$$$ and finishes at some node $$$v$$$ and it passes on every other node that lies on the shortest path between nodes $$$u$$$ and $$$v$$$, and the cost of the trip is the total cost of roads which the trip uses them.

The $$$m$$$ trips run individually which means the second trip starts when the first trip finishes, the third trip starts when the second trip finishes, and so on.

You have to calculate the total cost of the $$$m$$$ trips if we have chosen the set $$$S$$$ optimally.