석주가 회장으로 있는 SPARCS Company 에서 신제품 N종을 내놓기로 결정하였다! SPARCS Company 의 K명의 베타테스터들은 서로 협의하여 각각의 신제품에 대해 0점 이상 100점 이하의 정수인 평점을 메겨놓았다.</p>

베타테스트 결과가 궁금했던 경쟁사 GoN Company 소속 스파이 지훈이는 베타테스터 K명 각각에게 질문을 해서 평점에 대한 정보를 한 가지씩 얻을 수 있었다. 지훈이가 얻은 정보에는 세 가지 종류가 있다:

1. 1 a b c : (a 번 제품의 평점) - (b 번 제품의 평점) ≥ c 이다.
2. 2 a b c : (a 번 제품의 평점) - (b 번 제품의 평점) ≤ c 이다.
3. 3 a b c : (a 번 제품의 평점) - (b 번 제품의 평점) = c 이다.

지훈이는 이 데이터를 바탕으로 가장 평이 좋은 신제품과 평이 가장 좋지 않은 신제품을 알아내려고 하였으나, 그것을 알아내는 것은 무리였다. 아쉬운 대로 (가장 높은 평점) - (가장 낮은 평점)의 최솟값을 구해보자.

입력 형식

첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 1000, 1 ≤ K ≤ 3000)</p>

둘째 줄부터 K+1번째 줄에 지훈이가 얻은 정보들이 본문과 같은 형식으로 주어진다. (1 ≤ a ≤ N, 1 ≤ b ≤ N, |c| ≤ 100)

출력 형식

지훈이가 얻은 정보를 모두 만족하는 (가장 높은 평점) - (가장 낮은 평점)의 최솟값을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

3 1
1 2 3 3

예제 출력

3