스파이

석주가 회장으로 있는 SPARCS Company가 신제품 $N$종을 내놓기로 했다. 베타테스터 $K$명은 서로 협의해 각 신제품에 0점 이상 100점 이하의 정수 평점을 매겨 두었다.

경쟁사 GoN Company의 스파이 지훈이는 베타테스터 $K$명에게 각각 질문을 던져 평점에 관한 정보를 하나씩 얻어냈다. 정보의 종류는 세 가지다.

1. 1 a b c : ($a$번 제품의 평점) $-$ ($b$번 제품의 평점) $\ge c$
2. 2 a b c : ($a$번 제품의 평점) $-$ ($b$번 제품의 평점) $\le c$
3. 3 a b c : ($a$번 제품의 평점) $-$ ($b$번 제품의 평점) $= c$

지훈이는 이 정보로 평이 가장 좋은 제품과 가장 나쁜 제품을 가려내려 했지만 거기까지는 알아내지 못했다. 대신 (가장 높은 평점) $-$ (가장 낮은 평점)의 최솟값을 구하자.

첫째 줄에 $N$과 $K$가 주어진다. ($2 \le N \le 1000$, $1 \le K \le 3000$)

둘째 줄부터 $K$개의 줄에 지훈이가 얻은 정보가 위 형식으로 한 줄에 하나씩 주어진다. ($1 \le a \le N$, $1 \le b \le N$, $|c| \le 100$)

모든 정보를 동시에 만족하면서 각 평점이 0 이상 100 이하의 정수인 평점 배정 가운데 (가장 높은 평점) $-$ (가장 낮은 평점)의 최솟값을 출력한다. 그런 배정이 하나도 없으면 -1을 출력한다.