시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB227644426.994%

문제

석주가 회장으로 있는 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, 1 ≤ K ≤ 3000)

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

출력

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

예제 입력 1

3 1
1 2 3 3

예제 출력 1

3

출처

University > KAIST > 2016 KAIST 6th ACM-ICPC Mock Competition G번

  • 문제를 만든 사람: jihoon