为了避开圣诞市场的喧嚣，你计划去威尼斯旅行，欣赏那里美丽的运河和众多的桥梁。不幸的是，你似乎并不是唯一有这个计划的人，威尼斯最近决定对这一乐趣进行收费。因此，你决定每座桥只穿过一次就足够了。幸运的是，仅通过街道（不经过任何桥梁）就可以从任意一个地点到达其他任何地点。有趣的是，仅通过街道，从任意一个地点到另一个地点恰好只有一条路径。

在了解了所有这些信息之后，现在剩下的就是规划一次恰好穿过每座桥一次的旅行。为了让旅程更有趣，你还希望每条街道最多只使用一次。最短的可能旅行长度是多少？请注意，你的旅行可以从你选择的任何地方开始，但必须在开始的地方结束。

图 C.1：样例输入 1 的说明，其中一条路径长度为 45。

输入格式

输入包含以下内容：

• 第一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示威尼斯的地点数量。
• 接下来的 $n - 1$ 行，每行包含三个整数 $a$、$b$ 和 $w$ ($1 \le a, b \le n, a \ne b, 1 \le w \le 10^6$)，表示每条街道的起点、终点及其长度。
• 接下来的一行包含一个整数 $m$ ($1 \le m \le 5 \cdot 10^5$)，表示威尼斯的桥梁数量。
• 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \ne b$)，表示每座桥连接的两个地点。

桥梁很短，因此长度为零。

保证在不使用任何桥梁的情况下，可以从任意一个地点到达其他任何地点。此外，没有桥梁连接两个直接由街道相连的地点，且所有桥梁都连接不同的地点对。最后，保证至少存在一条恰好穿过每座桥一次且每条街道最多使用一次的闭回路。

输出格式

输出穿过所有桥梁且每条街道最多使用一次的最短闭回路的长度。

样例

输入样例 1

8
5 1 8
5 2 1
2 7 2
4 2 4
3 1 16
1 6 32
8 4 64
3
7 4
3 6
3 7

输出样例 1

45

输入样例 2

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

输出样例 2

0