题目描述

题目译自 CCC 2018 S5「Maximum Strategic Savings」

有 $N$ 个星球，编号为 $1\ldots N$。每个星球有 $M$ 座城市，编号为 $1\ldots M$。我们将 $e$ 星球上的城市 $f$ 记作 $(e,\,f)$。

有 $N\times P$ 条双向航线，对于每个星球 $e(1\le e\le N)$，有 $P$ 条航线，编号为 $1$ 到 $P$。第 $i$ 条航线连接城市 $(e,\,a_i)$ 和 $(e,\,b_i)$，且每天需要花费 $c_i$ 的代价维护。

有 $M\times Q$ 个双向港口。对于所有编号为 $f(1\le f\le M)$ 的城市，有 $Q$ 个港口，编号为 $1$ 到 $Q$。第 $j$ 个港口可以连接城市 $(x_j,\,f)$ 和 $(y_j,\,f)$，且每天需要花费 $z_j$ 的代价维护。

现在需要拆除一些港口和（或）取消一些航线，使得城市之间仍能保持联通，且节省的代价之和最大。

输入格式

第一行四个整数，分别为 $N,\,M,\,P,\,Q\ (0\le N,\,M,\,P,\,Q\le10^5)$。

接下来 $P$ 行，每行三个整数 $a_i,\,b_i,\,c_i(1\le a_i,\,b_i\le M,\,1\le c_i\le10^8)$。

再接下来 $Q$ 行，每行三个整数 $x_j,\,y_j,\,z_j(1\le x_j,\,y_j\le N,\,1\le z_j\le 10^8)$。

数据保证城市之间两两联通，可能有重边或自环。

输出格式

输出一行一个整数表示每天最多能节省的代价之和。

2 2 1 2
1 2 1
2 1 1
2 1 1

3

2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5

41

提示

样例 2 解释

一种可行的最优解是关闭城市 $(1,\,1)$ 与 $(1,1)$、$(2,\,1)$ 与 $(2,\,1)$、$(1,\,1)$ 与 $(1,\,2)$、$(1,\,3)$ 与 $(1,\,2)$、$(2,\,3)$ 与 $(2,\,2)$ 之间的航线；并关闭城市 $(2,\,3)$ 与 $(1,\,3)$ 间的港口。最终可以节省 $8 + 8 + 6 + 7 + 7 + 5 = 41$ 的代价。

对于 $\frac{2}{15}$ 的数据，$P,\,Q\le100$，且对于所有的 $1\le i\le P$，都有 $c_i=1$；对于所有的 $1\le j\le Q$，都有 $z_j=1$；

对于另外 $\frac{2}{15}$ 的数据，$P,\,Q\le 200$；

对于另外 $\frac{5}{15}$ 的数据，$N,\,M\le 200$；

对于全部的数据，$1\le N,\,M,\,P,\,Q\le10^5$。