P4809 [CCC 2018] Maximum Strategic Savings

**This problem is translated from [CCC 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) S5 “[Maximum Strategic Savings](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%201/seniorEF.pdf)”.** There are $N$ planets, numbered $1\ldots N$. Each planet has $M$ cities, numbered $1\ldots M$. We denote city $f$ on planet $e$ as $(e,\,f)$. There are $N\times P$ undirected flight routes. For each planet $e(1\le e\le N)$, there are $P$ routes, numbered from $1$ to $P$. Route $i$ connects cities $(e,\,a_i)$ and $(e,\,b_i)$, and it costs $c_i$ per day to maintain. There are $M\times Q$ undirected ports. For every city index $f(1\le f\le M)$, there are $Q$ ports, numbered from $1$ to $Q$. Port $j$ can connect cities $(x_j,\,f)$ and $(y_j,\,f)$, and it costs $z_j$ per day to maintain. Now you need to remove some ports and/or cancel some flight routes such that all cities are still connected, and the total saved cost is maximized.

The first line contains four integers $N,\,M,\,P,\,Q\ (0\le N,\,M,\,P,\,Q\le10^5)$. The next $P$ lines each contain three integers $a_i,\,b_i,\,c_i(1\le a_i,\,b_i\le M,\,1\le c_i\le10^8)$. The next $Q$ lines each contain three integers $x_j,\,y_j,\,z_j(1\le x_j,\,y_j\le N,\,1\le z_j\le 10^8)$. The testdata guarantees that all cities are connected to each other. There may be multiple edges or self-loops.

Output one integer on a single line, representing the maximum total cost that can be saved per day.

#### Explanation for Sample 2 One possible optimal solution is to close the flight routes between cities $(1,\,1)$ and $(1,1)$, $(2,\,1)$ and $(2,\,1)$, $(1,\,1)$ and $(1,\,2)$, $(1,\,3)$ and $(1,\,2)$, and $(2,\,3)$ and $(2,\,2)$; and close the port between cities $(2,\,3)$ and $(1,\,3)$. In the end, you can save a cost of $8 + 8 + 6 + 7 + 7 + 5 = 41$. For $\frac{2}{15}$ of the testdata, $P,\,Q\le100$, and for all $1\le i\le P$, $c_i=1$; for all $1\le j\le Q$, $z_j=1$. For another $\frac{2}{15}$ of the testdata, $P,\,Q\le 200$. For another $\frac{5}{15}$ of the testdata, $N,\,M\le 200$. For all testdata, $1\le N,\,M,\,P,\,Q\le10^5$. Translated by ChatGPT 5