#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/09

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/maang/problems/09

Repovive

Network Wiring Budget - MAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG09. Network Wiring Budget

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given $N$ nodes and $M$ existing bidirectional edges (which are free to use), plus a list of $K$ possible new edges each with an associated cost, find the minimum total cost to make all $N$ nodes connected (i.e., form a single connected component).

If the nodes are already connected using only existing edges, output $0$ . If it is impossible to connect all nodes even after using all available new edges, output $-1$ .

Constraints

$1 \le N \le 10^5$
$0 \le M \le 2 \times 10^5$
$0 \le K \le 2 \times 10^5$
$1 \le u, v \le N$ , $u \ne v$
$1 \le w \le 10^6$

Input

\begin{array}{l} N \quad M \quad K \\ u_1 \quad v_1 \\ \vdots \\ u_M \quad v_M \\ a_1 \quad b_1 \quad w_1 \\ \vdots \\ a_K \quad b_K \quad w_K \end{array}

Output

$ans$

Samples

Input

Explanation

There are 5 nodes. Existing edges connect $\{1,2\}$ and $\{3,4\}$ , and node 5 is isolated. We need to connect all three components. The cheapest new edge is $(4,5)$ with cost 3, merging node 5 into $\{3,4\}$ . Next cheapest is $(2,3)$ with cost 5, merging the two large components. Total cost: $3 + 5 =$ 8.

Output

Input

Explanation

All 3 nodes are already connected via existing edges: $1-2$ and $2-3$ . No new edges are needed. Answer: 0.

Output

Input

4 1 1
1 2
1 2 5

Explanation

Nodes $\{1,2\}$ are connected by the existing edge. Nodes 3 and 4 are isolated. The only available new edge connects 1 and 2 again, which does not help. It is impossible to connect all nodes. Answer: -1.

Output

-1

If the nodes are already connected using only existing edges, output $0$ . If it is impossible to connect all nodes even after using all available new edges, output $-1$ .

Constraints

$1 \le N \le 10^5$
$0 \le M \le 2 \times 10^5$
$0 \le K \le 2 \times 10^5$
$1 \le u, v \le N$ , $u \ne v$
$1 \le w \le 10^6$

\begin{array}{l} N \quad M \quad K \\ u_1 \quad v_1 \\ \vdots \\ u_M \quad v_M \\ a_1 \quad b_1 \quad w_1 \\ \vdots \\ a_K \quad b_K \quad w_K \end{array}

$ans$

All 3 nodes are already connected via existing edges: $1-2$ and $2-3$ . No new edges are needed. Answer: 0.