시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 87 17 14 21.538%

문제

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

베타테스트 결과가 궁금했던 경쟁사 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, K <= 3000)

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

출력

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

예제 입력

3 1
1 2 3 3

예제 출력

3

힌트