밥 먹기

소들이 밥을 먹으려고 번호 순서대로 일직선 위에 줄을 선다. 선영이는 소를 $N$마리 ($2 \le N \le 1{,}000$) 기르고 있으며, 각 소에는 $1$번부터 $N$번까지 번호가 붙어 있다. 소들은 번호가 커지는 순서대로 서므로, $i$번 소의 좌표를 $x_i$라 하면 $x_1 \le x_2 \le \cdots \le x_N$을 만족한다. 두 마리 이상의 소가 같은 좌표에 설 수도 있다.

서로 친한 소들은 일정 거리 이내로 붙어 있으려 하고, 서로 싫어하는 소들은 일정 거리 이상 떨어져 있으려 한다. 친한 소 쌍과 두 소가 떨어질 수 있는 최대 거리가 길이 $ML$ ($1 \le ML \le 10{,}000$)인 목록으로 주어지고, 이어서 싫어하는 소 쌍과 두 소가 떨어져 있어야 하는 최소 거리가 길이 $MD$ ($1 \le MD \le 10{,}000$)인 목록으로 주어진다.

이 모든 조건을 만족하도록 줄을 세울 수 있다면, $1$번 소와 $N$번 소 사이의 최대 거리를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $N$, $ML$, $MD$가 공백으로 구분되어 주어진다.

이어지는 $ML$개의 줄에는 각각 정수 $A$, $B$, $D$ ($1 \le A < B \le N$)가 공백으로 구분되어 주어진다. 이는 $A$번 소와 $B$번 소가 최대 $D$ ($1 \le D \le 1{,}000{,}000$)만큼 떨어질 수 있음을 뜻한다.

그 다음 $MD$개의 줄에는 각각 정수 $A$, $B$, $D$ ($1 \le A < B \le N$)가 공백으로 구분되어 주어진다. 이는 $A$번 소와 $B$번 소가 최소 $D$ ($1 \le D \le 1{,}000{,}000$)만큼 떨어져 있어야 함을 뜻한다.

첫째 줄에 $1$번 소와 $N$번 소 사이의 최대 거리를 출력한다. 조건을 만족하도록 줄을 세우는 것이 불가능하면 $-1$을, 최대 거리가 무한히 커질 수 있으면 $-2$를 출력한다.