Cheap Deliveries

Abu runs a delivery service that carries items from one city to another. One day Abu receives $k$ items to deliver. Each item must be carried from its start city to its destination city, and only one item can be carried at a time. The delivery order is free, as long as every item is delivered. Abu starts in the start city of some item, delivers it to its destination city, then moves to the start city of the next item and continues until no item remains.

Every road is bidirectional, and two cities may be connected by more than one road. Abu may use any road as many times as needed.

Given the list of cities, the roads between them with their lengths, and the list of deliveries, determine the minimum total travel distance needed to finish all deliveries in the most efficient order.

The first line contains three integers $n$, $m$ and $k$: the number of cities, the number of roads and the number of items ($2 \le n, m \le 10^4$, $1 \le k \le 18$).

Each of the next $m$ lines contains three integers $u_i$, $v_i$ and $l_i$ ($1 \le u_i, v_i \le 10^4$, $1 \le l_i \le 10^6$), meaning there is a road of length $l_i$ between city $u_i$ and city $v_i$.

Each of the next $k$ lines contains two integers $f_i$ and $d_i$ ($1 \le f_i, d_i \le 10^4$), meaning item $i$ must be delivered from city $f_i$ to city $d_i$.

Print a single integer: the minimum total travel distance when all items are delivered in the optimal order, or $-1$ if it is impossible to deliver all items.

In the first case, starting from city $5$ and delivering the third item to city $3$, then moving to city $1$ and delivering the second and first items in order, gives a total travel distance of $12$, which is optimal.

In the second case, cities $1$, $2$ and $4$ are disconnected from cities $3$ and $5$, so it is impossible to deliver all items.