设 $G$ 和 $H$ 为两个带权无向简单图。我们定义这两个图的笛卡尔积 $G \square H$ 为一个图，其顶点集为两个图顶点集的笛卡尔积 $V(G) \times V(H)$，且当且仅当满足以下条件时，顶点 $(u_1, v_1)$ 和 $(u_2, v_2)$ 之间存在一条边：

• $u_1 = u_2$，且 $G$ 中存在边 $(v_1, v_2)$。在这种情况下，$G \square H$ 中的边 $((u_1, v_1), (u_2, v_2))$ 的权重与 $G$ 中边 $(v_1, v_2)$ 的权重相同。
• 或者 $v_1 = v_2$，且 $H$ 中存在边 $(u_1, u_2)$。在这种情况下，$G \square H$ 中的边 $((u_1, v_1), (u_2, v_2))$ 的权重与 $H$ 中边 $(u_1, u_2)$ 的权重相同。

给定两个连通图 $G$ 和 $H$，计算 $G \square H$ 的最小生成树的总权重。

输入格式

第一行包含四个整数 $n_1, m_1, n_2, m_2$ ($2 \le n_1, n_2 \le 10^5$; $1 \le m_1, m_2 \le 10^5$)，分别表示 $G$ 的顶点数、$G$ 的边数、$H$ 的顶点数以及 $H$ 的边数。

接下来的 $m_1$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($0 \le u_i, v_i \le n_1 - 1$; $1 \le w_i \le 10^8$)，描述 $G$ 中连接顶点 $u_i$ 和 $v_i$ 且权重为 $w_i$ 的一条边。

接下来的 $m_2$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($0 \le u_i, v_i \le n_2 - 1$; $1 \le w_i \le 10^8$)，描述 $H$ 中连接顶点 $u_i$ 和 $v_i$ 且权重为 $w_i$ 的一条边。

保证图 $G$ 和 $H$ 是简单且连通的。简单图是指没有自环，且任意两个顶点之间最多只有一条边的图。

输出格式

输出一个整数：$G \square H$ 的最小生成树的总权重。

样例

输入 1

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

输出 1

15