t2

【题目描述】

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

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

• 新图有 n_1*n_2 个结点，编号记作一个正整数对(x,y),1⩽x⩽n_1,1⩽y⩽n_2 ；

• 对于每条第一张图上的边 (u,v,w)，我们在所有新图的(u,i),(v,i)，1⩽i⩽n_2之间都连一条边权为 w 的边；

• 对于每条第二张图上的边(u,v,w) ，我们在所有新图的(i,u),(i,v),1⩽i⩽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⩽n_1,n_2⩽10^5,1⩽ m_1,m_2⩽ 3*10^5，边权在[1,10^8]之间，保证两张图均连通。

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

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

大样例

【来源】

核桃编程