Feeding Time

The cows line up in a single row in order of their numbers to wait for their food. Sunyeong owns $N$ cows ($2 \le N \le 1{,}000$), numbered from $1$ to $N$. Because the cows stand in increasing order of their numbers, if $x_i$ is the coordinate of cow $i$, then $x_1 \le x_2 \le \cdots \le x_N$. Two or more cows may stand at the same coordinate.

Cows that like each other want to stay within a certain distance, while cows that dislike each other want to stay at least a certain distance apart. You are given a list of length $ML$ ($1 \le ML \le 10{,}000$) describing pairs of cows that like each other together with the maximum distance the two may be apart, followed by a list of length $MD$ ($1 \le MD \le 10{,}000$) describing pairs of cows that dislike each other together with the minimum distance the two must be apart.

Write a program that, if the cows can be lined up so that all of these conditions hold, computes the maximum possible distance between cow $1$ and cow $N$.

The first line contains the integers $N$, $ML$, and $MD$, separated by spaces.

Each of the next $ML$ lines contains three integers $A$, $B$, and $D$ ($1 \le A < B \le N$), meaning that cow $A$ and cow $B$ may be at most $D$ ($1 \le D \le 1{,}000{,}000$) apart.

Each of the following $MD$ lines contains three integers $A$, $B$, and $D$ ($1 \le A < B \le N$), meaning that cow $A$ and cow $B$ must be at least $D$ ($1 \le D \le 1{,}000{,}000$) apart.

Print the maximum distance between cow $1$ and cow $N$ on the first line. Print $-1$ if it is impossible to line the cows up under the given conditions, or $-2$ if the maximum distance can be arbitrarily large (infinite).