老牧场主 Tom 管理着 $n$ 个农场，他计划修建几条新路以使他的农场连通。 为此，一家建筑公司提供了 $m$ 个建设方案，每个方案由三个整数 $a, b$ 和 $c$ 描述，表示修建一条连接第 $a$ 个农场和第 $b$ 个农场的路需要花费 $c$ 美元。

然而，最终的决策必须满足 $q$ 个额外的约束条件。每个约束包含两个整数 $u$ 和 $v$，要求 Tom 必须至少选择第 $u$ 个方案和第 $v$ 个方案中的一个。

由于预算紧张，Tom 希望最小化总花费。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $m$ ($1 \le m \le 5 \times 10^5$)，分别表示农场的数量和方案的数量。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $a, b$ ($1 \le a, b \le n$) 和 $c$ ($1 \le c \le 10^3$)，表示通过第 $i$ 个方案修建一条连接第 $a$ 个农场和第 $b$ 个农场的路，花费为 $c$ 美元。

下一行包含一个整数 $q$ ($0 \le q \le 16$)，表示约束条件的数量。

接下来的 $q$ 行中，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le m$)，表示一个约束条件，即 Tom 必须至少选择第 $u$ 个方案和第 $v$ 个方案中的一个。

输出格式

如果可以通过修建新路使所有农场连通，则输出一行一个整数，表示 Tom 需要支付的最小总花费；否则输出 $-1$。

样例

样例输入 1

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

样例输出 1

11