题目描述

有 $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)$。

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

输出格式

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

样例 1

输入

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

输出

3

样例 2

输入

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

输出

41

一种可行的最优解是关闭城市 $(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$。