Two friends, Alisa and Yuki, planted a tree withvertices in their garden. A tree is an undirected graph without cycles, loops, or multiple edges. Each edge in this tree has a length of . Initially, vertex is the root of the tree.
Alisa and Yuki are growing the tree not just for fun, they want to sell it. The cost of the tree is defined as the maximum distance from the root to a vertex among all vertices of the tree. The distance between two vertices and is the sum of the lengths of the edges on the path from to .
The girls took a course in gardening, so they know how to modify the tree. Alisa and Yuki can spend neighbors of the current root. This operation can be performed any number of times (possibly zero). Note that the structure of the tree is left unchanged; the only change is which vertex is the root.coins to shift the root of the tree to one of the
The friends want to sell the tree with the maximum profit. The profit is defined as the difference between the cost of the tree and the total cost of operations.
Help the girls and find the maximum profit they can get by applying operations to the tree any number of times (possibly zero).
The first line of the input contains one integer( ) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains integers, , ( ; ) — the number of vertices in the tree, the length of each edge, and the cost of the operation.
The nextlines of the test case contain pairs of integers , ( ) — the edges of the graph. These edges form a tree.
The sum of the values ofover all test cases does not exceed .