EOJ Delivery Service Company handles a massive amount of orders in our nation. As is well known, our nation has cities, with bi-directional paths connecting them, forming a tree. The length of the -th path is , meaning that the time we have to spend walking through this path is .
Now, you, as the headquarter of EOJ, has somehow learned a magic spell. Each time you cast a spell on two paths, the lengths of these two paths magically swap with each other. You can do this magic as many times as you want (possibly none).
We have orders waiting to be handled. The -th order demands sending a package from city to city . We kindly ask you to do your magic before all the deliveries start, such that the total time we have to spend on delivering these packages is minimized.
输入格式
The first line of the input contains one single integer ().
The next lines tell about the path information from path to path , the -th of which contains three space-separated integers , and (, , ).
The next line contains one integer ().
The next lines each contains two space-separated integers and ().
输出格式
Output one integer, the minimum total time you can achieve.
提示
In the example, we swap the weights between edge and , so that the first order takes time units to complete; the second order takes time units. Thus the total time is .