题目描述

观者有两张图，分别有 $n_1,n_2$ 个点与 $m_1,m_2$ 条边，并保证这两张图无重边与自环。

她根据这两张图生成了一张新图，生成规则如下：

• 新图有 $n_1\times n_2$ 个结点，编号记作一个正整数对 $(x,y),1\leqslant x\leqslant n_1,1\leqslant y\leqslant n_2$；
• 对于每条第一张图上的边 $(u,v,w)$，我们在所有新图的 $(u,i),(v,i),1\leqslant i\leqslant n_2$ 之间都连一条边权为 $w$ 的边；
• 对于每条第二张图上的边 $(u,v,w)$，我们在所有新图的 $(i,u),(i,v),1\leqslant i\leqslant n_1$ 之间都连一条边权为 $w$ 的边。

观者想知道这张新图的最小生成树的边权和，请你告诉她。

输入格式

第一行四个正整数 $n_1,n_2,m_1,m_2$。

接下来 $m_1$ 行每行三个正整数，表示第一张图中一条边的两个顶点与边权。

接下来 $m_2$ 行每行三个正整数，表示第二张图中一条边的两个顶点与边权。

输出格式

一行一个正整数，表示答案。

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

29

数据范围

对于 $100\%$ 的数据，$2\leqslant n_1,n_2\leqslant 2\times 10^5,1\leqslant m_1,m_2\leqslant 3\times 10^5$，边权在 $[1,10^8]$ 之间，保证两张图均连通。

特殊性质 A：保证 $m_1=n_1-1,m_2=n_2-1$，且每个结点度数不超过 $2$。

特殊性质 B：保证两张图边集完全一致（对应标号的边顶点与边权均相同）。

样例

样例