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 \le e \le 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 \le f \le M)\), there are \(Q\)
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?

\((1 \le e \le N)\)
\((1 \le f \le M)\)
\((1\le N,M,P,Q \le 10^5)\)
\((1 \le a_i, b_i \le M, 1 \le c_i \le 10^8)\)
\((1 \le x_j, y_j \le N, 1 \le z_j \le 10^8)\)
\(P,Q \le 100\)
\(1 \le i \le P\)
\(1 \le j \le Q\)
\(P,Q \le 200\)
\(N,M \le 200\)

The first line contains four space-separated integers \(N\), \(M\), \(P\), \(Q\)
\((1\le N,M,P,Q \le 10^5)\).

Then \(P\) lines follow; the \(i\)-th one contains three space-separated
integers \(a_i\), \(b_i\), \(c_i\) \((1 \le a_i, b_i \le M, 1 \le c_i \le 10^8)\).

Then \(Q\) lines follow; the \(j\)-th one contains three space-separated
integers \(x_j\), \(y_j\), \(z_j\) \((1 \le x_j, y_j \le N, 1 \le z_j \le 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.

For 2 of the 15 available marks, \(P,Q \le 100\) and \(c_i = 1\) for all
\(1 \le i \le P\), and \(z_j = 1\) for all \(1 \le j \le Q\).

For an additional 2 of the 15 available marks, \(P,Q \le 200\).

For an additional 5 of the 15 available marks, \(N,M \le 200\).

Output a single integer, the maximum sum of energy that can be saved
daily.

생성자가 기록되지 않았습니다.

출처 CCC 2018 Senior