Mobile Phone Network
Contest: Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Difficulty rating: 2600
Tags: dfs and similar, dsu, graphs, trees

You are managing a mobile phone network, and want to offer competitive prices to connect a network.

The network has $$$n$$$ nodes.

Your competitor has already offered some connections between some nodes, with some fixed prices. These connections are bidirectional. There are initially $$$m$$$ connections the competitor is offering. The $$$i$$$-th connection your competitor is offering will connect nodes $$$fa_i$$$ and $$$fb_i$$$ and costs $$$fw_i$$$.

You have a list of $$$k$$$ connections that you want to offer. It is guaranteed that this set of connection does not form any cycle. The $$$j$$$-th of these connections will connect nodes $$$ga_j$$$ and $$$gb_j$$$. These connections are also bidirectional. The cost of these connections have not been decided yet.

You can set the prices of these connections to any arbitrary integer value. These prices are set independently for each connection. After setting the prices, the customer will choose such $$$n - 1$$$ connections that all nodes are connected in a single network and the total cost of chosen connections is minimum possible. If there are multiple ways to choose such networks, the customer will choose an arbitrary one that also maximizes the number of your connections in it.

You want to set prices in such a way such that all your $$$k$$$ connections are chosen by the customer, and the sum of prices of your connections is maximized.

Print the maximum profit you can achieve, or $$$-1$$$ if it is unbounded.

Input format:
The first line of input will contain three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \leq n, k, m \leq 5 \cdot 10^5, k \leq n-1$$$), the number of nodes, the number of your connections, and the number of competitor connections, respectively.

The next $$$k$$$ lines contain two integers $$$ga_i$$$ and $$$gb_i$$$ ($$$1 \leq ga_i, gb_i \leq n$$$, $$$ga_i \not= gb_i$$$), representing one of your connections between nodes $$$ga_i$$$ and $$$gb_i$$$. Your set of connections is guaranteed to be acyclic.

The next $$$m$$$ lines contain three integers each, $$$fa_i$$$, $$$fb_i$$$ and $$$fw_i$$$ ($$$1 \leq fa_i, fb_i \leq n$$$, $$$fa_i \not= fb_i$$$, $$$1 \leq fw_i \leq 10^9$$$), denoting one of your competitor's connections between nodes $$$fa_i$$$ and $$$fb_i$$$ with cost $$$fw_i$$$. None of these connections connects a node to itself, and no pair of these connections connect the same pair of nodes. In addition, these connections are given by non-decreasing order of cost (that is, $$$fw_{i-1} \leq fw_i$$$ for all valid $$$i$$$).

Note that there may be some connections that appear in both your set and your competitor's set (though no connection will appear twice in one of this sets).

It is guaranteed that the union of all of your connections and your competitor's connections form a connected network.

Output format:
Print a single integer, the maximum possible profit you can achieve if you set the prices on your connections appropriately. If the profit is unbounded, print $$$-1$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample, it's optimal to give connection $$$1-3$$$ cost $$$3$$$, connection $$$1-2$$$ cost $$$3$$$, and connection $$$3-4$$$ cost $$$8$$$. In this case, the cheapest connected network has cost $$$14$$$, and the customer will choose one that chooses all of your connections.

In the second sample, as long as your first connection costs $$$30$$$ or less, the customer chooses both your connections no matter what is the cost of the second connection, so you can get unbounded profit in this case.

Example input:
4 3 6
1 2
3 4
1 3
2 3 3
3 1 4
1 2 4
4 2 8
4 3 8
4 1 10

Example output:
14

Example input:
3 2 1
1 2
2 3
1 2 30

Example output:
-1

Editorial:
Consider the forest of your edges.
Let's add edges into this forest greedily from our competitor's set in order of increasing weight until we have a spanning tree. Remember, we don't need to sort, the input is already given in sorted order.
Now, consider the competitor's edges one by one by increasing weight. Since we have a spanning tree, each competitor edge spans some path on our tree.
To process a competitor's edge, we can collapse all the nodes in the path into one single large node, and fix the cost of our edges along this path to be equal to the cost of the currently considered competitor's edge. We know this is an upper bound on cost since if any were higher, then by the cycle property of MSTs, the customer can ignore one of the higher cost edge on this cycle and choose the customer's edge instead.
In addition, this still allows us to satisfy the condition of the customer choosing all of our edges, since by Kruskal's algorithm, the customer will try to greedily add our edges first into their spanning tree and won't be able to add the customer edge since it now forms a cycle). This shows that this cost is the maximum possible profit since we have an upper bound on each edge, and this upper bound also gives a valid solution.
To determine if our answer can be unbounded, we can check if any of our edges remains uncollapsed after processing all competitor edges.
To do this efficiently, we can just do it naively (even without needing to compute LCAs!).
To show it's already fast enough, there are only a total of at most $$$n$$$ merges overall and each merge can be done in $$$\alpha(n)$$$ time, where $$$\alpha(n)$$$ is the inverse ackermann function, so the overall complexity is $$$O(m + (n + k)\alpha(n))$$$. Unfortunately, this is too hard to separate from solution with logarithms, so those were also allowed to pass (though TL might have been a bit more strict in those cases).