석주가 회장으로 있는 SPARCS Company 에서 신제품 \(N\)종을 내놓기로 결정하였다! SPARCS Company 의 \(K\)명의 베타테스터들은 서로 협의하여 각각의 신제품에 대해 0점 이상 100점 이하의 정수인 평점을 메겨놓았다. 베타테스트 결과가 궁금했던 경쟁사 GoN Company 소속 스파이 지훈이는 베타테스터 \(K\)명 각각에게 질문을 해서 평점에 대한 정보를 한 가지씩 얻을 수 있었다. 지훈이가 얻은 정보에는 세 가지 종류가 있다:

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

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

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

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

riseoj 작성

출처 Online Judge > BOJ