410446: GYM104022 D Farm

Tom, an old rancher who manages $$$n$$$ farms, is planning several new roads to make his farms connected.

For this purpose, an architecture company provides $$$m$$$ building plans, each of which is described by three integers $$$a$$$, $$$b$$$ and $$$c$$$ representing that it would cost $$$c$$$ dollars to build a new road connecting the $$$a$$$-th and the $$$b$$$-th farms.

However, the final decision has to satisfy $$$q$$$ more constraints. A constraint contains two integers $$$u$$$ and $$$v$$$, which requires that Tom must choose at least one of the $$$u$$$-th and the $$$v$$$-th plans.

Because of a looming budget shortfall, Tom prefers to minimize the total cost.

The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$m$$$ $$$(1 \leq m \leq 5 \times 10^5)$$$, indicating the number of farms and the number of plans.

In the next $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$a$$$, $$$b$$$ $$$(1 \leq a, b \leq n)$$$ and $$$c$$$ $$$(1 \leq c \leq 10^3)$$$, which means that the cost of building a road that connects the $$$a$$$-th and the $$$b$$$-th farms via the $$$i$$$-th plan is $$$c$$$ dollars.

The next line contains an integer $$$q$$$ $$$(0 \leq q \leq 16)$$$, indicating the number of constraints.

In the next $$$q$$$ lines, each line contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq m)$$$, indicating a constraint that Tom must choose at least one of the $$$u$$$-th and the $$$v$$$-th plans.

If it is possible to connect all farms via building new roads, output an integer in a line representing the minimum total cost that Tom will pay, or otherwise output $$$-1$$$.

4 6
1 1 2
2 4 3
1 1 4
2 4 4
3 2 4
1 3 4
1
1 2

11