**46 人解决**，54 人已尝试。

**61 份提交通过**，共有 197 份提交。

**3.8** EMB 奖励。

**单点时限: **2.5 sec

**内存限制: **512 MB

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.

Input

5 1 2 2 1 3 3 3 4 3 3 5 4 2 1 5 4 2

Output

14

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 .

**46 人解决**，54 人已尝试。

**61 份提交通过**，共有 197 份提交。

**3.8** EMB 奖励。