10230: CCC '18 S5 - Maximum Strategic Savings
[Creator : ]
Description
A long time ago in a galaxy far, far away, there are $N$ planets numbered from 1 to N. Each planet has $M$ cities numbered from 1 to M. Let city $f$ of planet $e$ be denoted as $(e,f)$.
There are $N\times P$ two-way flights in the galaxy. For every planet $e\ (1≤e≤N)$, there are $P$ flights numbered from 1 to P. Flight $i$ connects cities $(e,a_i)$ and $(e,b_i)$ and costs $c_i$ energy daily to maintain.
There are $M\times Q$ two-way portals in the galaxy. For all cities with number $f\ (1≤f≤M)$, there are $Q$ two-way portals numbered from 1 to Q. Portal $j$ connects cities $(x_j,f)$ and $(y_j,f)$ and costs $z_j$ energy daily to maintain.
It is possible to travel between any two cities in the galaxy using only flights and/or portals.
Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut down to save as much energy as possible, but it should remain possible to travel between any two cities afterwards.
What is the maximum sum of energy that can be saved daily?
There are $N\times P$ two-way flights in the galaxy. For every planet $e\ (1≤e≤N)$, there are $P$ flights numbered from 1 to P. Flight $i$ connects cities $(e,a_i)$ and $(e,b_i)$ and costs $c_i$ energy daily to maintain.
There are $M\times Q$ two-way portals in the galaxy. For all cities with number $f\ (1≤f≤M)$, there are $Q$ two-way portals numbered from 1 to Q. Portal $j$ connects cities $(x_j,f)$ and $(y_j,f)$ and costs $z_j$ energy daily to maintain.
It is possible to travel between any two cities in the galaxy using only flights and/or portals.
Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut down to save as much energy as possible, but it should remain possible to travel between any two cities afterwards.
What is the maximum sum of energy that can be saved daily?
Input
The first line contains four space-separated integers $N,M,P,Q\ (1≤N,M,P,Q≤10^5)$.
Then $P$ lines follow; the $i$-th one contains three space-separated integers $a_i,b_i,c_i\ (1≤a_i,b_i≤M,\ 1≤c_i≤10^8)$.
Then $Q$ lines follow; the $j$-th one contains three space-separated integers $x_j,y_j,z_j\ (1≤x_j,y_j≤N,\ 1≤z_j≤10^8)$.
It is guaranteed that it will be possible to travel between any two cities using flights and/or portals. There may be multiple flights/portals between the same pair of cities or a flight/portal between a city and itself.
Then $P$ lines follow; the $i$-th one contains three space-separated integers $a_i,b_i,c_i\ (1≤a_i,b_i≤M,\ 1≤c_i≤10^8)$.
Then $Q$ lines follow; the $j$-th one contains three space-separated integers $x_j,y_j,z_j\ (1≤x_j,y_j≤N,\ 1≤z_j≤10^8)$.
It is guaranteed that it will be possible to travel between any two cities using flights and/or portals. There may be multiple flights/portals between the same pair of cities or a flight/portal between a city and itself.
Output
Output a single integer, the maximum sum of energy that can be saved daily.
Sample 1 Input
2 2 1 2
1 2 1
2 1 1
2 1 1
Sample 1 Output
3
Sample 2 Input
2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5
Sample 2 Output
41
One possible way is to shut down the flights between cities (1,1) and (1,1), (2,1) and (2,1), (1,1) and (1,2), (1,3) and (1,2), (2,3) and (2,2), and shut down the portal between cities (2,3) and (1,3) for total energy savings of 8+8+6+7+7+5=41.