Shelter

In a dimly lit room, at about 23:55, Milan sits at a three-legged table and thinks about the possible consequences a nuclear disaster would have on his city. As mayor, he knows all the relevant facts well.

The city has exactly $N$ residents, and each resident lives in a house of their own. Exactly $M$ pairs of houses are connected by roads, and the time needed to travel each road is known. Exactly $K$ houses contain atomic shelters, and the capacity of each shelter is known. Milan keeps asking himself: "What is the minimum time needed to evacuate all residents of this city?"

Evacuation means that every resident ends up in some atomic shelter. Residents move optimally (along shortest paths), and several people may move along the same road at the same time in different directions. You may also assume that any two houses are connected by a path that uses some subset of the given roads.

The first line contains natural numbers $N$ ($1 \le N \le 100000$), $M$ ($1 \le M \le 300000$), and $K$ ($1 \le K \le 17$), which are the number of residents, the number of roads, and the number of shelters. Houses are numbered from 1 to $N$.

Each of the next $M$ lines contains three natural numbers $A$, $B$ ($1 \le A, B \le N$, $A \ne B$), and $C$ ($1 \le C \le 10^9$). This means there is a road between houses $A$ and $B$, and passing through it takes $C$ units of time.

Each of the next $K$ lines contains two natural numbers $X$ ($1 \le X \le N$) and $Y$ ($1 \le Y \le 10^9$). This means house $X$ has an atomic shelter that can hold at most $Y$ people. The total capacity of all shelters is at least $N$.

Print one line with the minimum time needed to evacuate all residents of the city.

In the first sample, within 3 units of time, the people from houses 1, 2, and 3 can reach the shelter in house 1, and the people from houses 4 and 5 can reach the shelter in house 4. A shorter time is not enough for everyone to reach a shelter, because the shelter in house 4 holds at most two people.