Description

妖怪之山上有 $n$ 个地点，鸦天狗和河童的两套交通线路都是分别由一些连接这些地点的无向道路组成的，每条道路有自己的长度，把这些道路看成有权边，那么他们的两套线路分别可以表示成两棵 $n$ 个节点的树 $T_1, T_2$（有 $n-1$ 条边的有边权无向连通图），河童重工现在要新建一些无向道路，新建一条无向道路 $(i,j)$ 的花费是 $dist_{T_1}(i,j)+dist_{T_2}(i,j)$（即 $T_1,T_2$ 上 $i$ 到 $j$ 的距离之和），河童重工要保证妖怪之山的任意两个节点都能只通过新修建的道路互相到达。但由于如果花费过多可能引起异变，所以他们希望这个工程的总花费最少。

荷取作为这个工程的总设计师，请你帮她算一算，修建新道路的总花费最少是多少？

Input Format

第一行一个正整数 $n$，表示节点数量。

接下来有 $n-1$ 行，其中第 $i$ 行有三个整数 $x_i, y_i, v_i(1 \leq x_i, y_i \leq n, 1 \leq v_i \leq 5000)$，表示 $T_1$ 中有一条长度为 $v_i$ 的边，连接 $x_i, y_i$ 两点。

接下来有 $n-1$ 行，其中第 $j$ 行有三个整数 $x_j, y_j, v_j(1 \leq x_j, y_j \leq n, 1 \leq v_j \leq 5000)$，表示 $T_2$ 中有一条长度为 $v_j$ 的边，连接 $x_j, y_j$ 两点。

Output Format

一行一个整数表示最少的总花费。

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

10

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

8

Hint

对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^5$。

本题共有 $5$ 个子任务，每个子任务的限制如下：

子任务 $1$（$15$ 分)：保证 $2 \leq n \leq 1000$。

子任务 $2$（$15$ 分)：保证 $T_1, T_2$ 分别是一条链。

子任务 $3$（$5$ 分)：保证 $T_1, T_2$ 除了边权完全相同（即如果将两棵树看成无边权树，那么它们是相同的）。

子任务 $4$（$5$ 分)：保证 $T_2$ 是一条链。

子任务 $5$（$60$ 分)：无特殊限制。