Description

Original source: USACO 2005 Dec. Gold

FJ has $N$ cows $(2\le N\le 1000)$, numbered $1\ldots N$. The cows will line up in order of their numbers (multiple cows may occupy the same position). In other words, assuming the $i$-th cow is at position $P_{\!\;i}$, then $P_{\,1}\le P_{\,2}\le \ldots\le P_{\!\;N}$.

Some cows are good buddies and want the distance between them to be less than or equal to a certain number. Some cows are rivals and want the distance between them to be greater than or equal to a certain number.

Given $M_L$ pairs of good buddies, along with the maximum distance they desire between each other; and $M_D$ pairs of rivals, along with the minimum distance they desire between each other $(1\le M_L,$ $M_D\le 10^4)$.

Calculate: If all the above conditions are satisfied, what is the maximum possible distance between cow $1$ and cow $N$ ($P_{\!\;N}-P_{\,1}$).

Input Format

The first line: Three integers $N, M_L, M_D$, separated by spaces.
Lines $2\dots M_L+1$: Each line contains three integers $A, B, D$, separated by spaces, indicating $P_B-P_A\le D$.
Lines $M_L+2\dots M_L+M_D+1$: Each line contains three integers $A, B, D$, separated by spaces, indicating $P_B-P_A\ge D$.
It is guaranteed that $1\le A<B\le N,$ $1\le D\le 10^6$.

Output Format

One line with an integer. If there is no valid arrangement, output $\texttt{-1}$. If there is a valid arrangement but the distance between cow $1$ and cow $N$ can be infinitely large, output $\texttt{-2}$. Otherwise, output the maximum distance between cow $1$ and cow $N$.

Sample 1

The four cows are located at $0,7,10,27$ respectively.

4 2 1
1 3 10
2 4 20
2 3 3

27

Data Range and Hints

For all data, $2\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^6$.