Problem AP
Dragon Ball II

Photo by Pixabay

There used to be a legendary tale about Dragon Balls on Planet X: if one collects seven Dragon Balls, the Dragon God will show up and help you fulfill your wishes.

However, ever since a Dragon Ball radar was discovered, which pinpoints the location of each Dragon Ball, collecting all seven balls has become too easy, to the point that the Dragon God is pestered non-stop by frivolous wishes. He has had enough, and so wants to make the process of collecting the balls harder. Instead of seven balls, he has created a huge number, each with a (not necessarily distinct) serial number. To summon the Dragon God, you now need to collect seven Dragon Balls with pairwise distinct serial numbers: duplicate Balls do not help you.

You recently bought a Dragon Ball radar at a flea market, which tells you which city each Dragon Ball resides in, as well as that ball’s serial number. Can you still find the cheapest way to summon the Dragon God?

There are $n$ cities in total on the Planet X, numbered from $1$ to $n$. You are currently at city $1$. To travel from one city to another, you can take any of $m$ bidirectional teleport trips, as many times as you like. The $i$-th teleporter costs $t_ i$ coins to use each time, and it can teleport you between cities $a_ i$ and $b_ i$. To collect a Dragon Ball, you simply need to visit the city where it’s located, as indicated on your radar. It is possible that multiple Dragon Balls are at the same city; in this case you pick all of them all up at once if you visit that city.

Input

The first line of input contains three space-separated integers $n$, $m$, and $k$ $(1 \leq n, k \leq 1\, 000, 1 \le m \le 10\, 000)$, the number of cities, teleport trips, and Dragon Balls, respectively. Then follow $m$ lines containing three space-separated integers $a_ i$, $b_ i$, and $t_ i$ each $(1 \le a_ i, b_ i \le n, 0 \le t_ i \le 10\, 000)$, which, as explained above, represent the two cities connected by the teleport trip, and cost to use the teleporter.

Then follow $k$ lines, the $i$-th of which contains two space-separated integers $c_ i$ and $d_ i$ $(1 \le c_ i, d_ i \le n)$, indicating that the $i$-th Dragon Ball is located in city $c_ i$ and has serial number $d_ i$. Note that there might be multiple Dragon Balls located in the same city, multiple Dragon Balls that share the same serial number, or even multiple Dragon Balls with the same serial number in the same city.

Output

Print the minimum number of coins that you have to spend to collect seven Dragon Balls with pairwise distinct serial number. If there is no way to complete this task, print $-1$.

11 10 10
1 2 1
2 3 1
3 4 1
1 5 1
5 6 1
6 7 1
7 8 1
1 9 1
1 10 1
1 11 1
2 1
3 2
4 3
5 1
6 2
7 3
8 4
9 5
10 6
11 7

10