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

문제

본 문제와 Small 문제는 입력의 제한과 출력 조건이 다르다. ”입력”과 ”출력” 문단을 참조하라.

오래된 놀이공원의 주인인 인서는 놀이공원을 새롭게 단장하기 위해 자신의 가장 유능한 직원인 정우에게 리모델링을 지시하였다. 리모델링의 책임자가 된 정우는 우선 놀이공원의 상태를 아래와 같이 파악하였다.

  • 놀이공원에는 $N$개의 놀이기구와 $M$개의 공원포탈이 있다.
  • 놀이기구 $i$ $(1\le i\le N)$
    • 놀이기구 $i$의 주행시간은 $T_i$, 대기시간은 $P_i$이다. 이 $2$개의 시간은 놀이기구 $i$를 언제 타든 항상 동일하다.
    • 따라서 놀이기구 $i$에 도착해 놀이기구를 타고 내리면 총 $T_i+P_i$의 시간이 걸린다.
  • 공원포탈 $j$ $(1\le j\le M)$
    • 공원포탈 $j$를 이용하면 놀이기구 $u_j$에서 놀이기구 $v_j$로 이동할 수 있다. 반대로 놀이기구 $v_j$에서 놀이기구 $u_j$로 이동하는 것은 불가능하다.
    • 공원포탈 $j$를 이용하면 $S_j$만큼 시간이 소요된다.

정우는 위와 같은 놀이공원의 상태를 바탕으로 고객에 대해 아래와 같은 가설을 설립하였다.

  • 대기시간 $P_i$가 가장 작은 놀이기구 중 하나를 처음으로 타고, 대기시간 $P_i$가 가장 큰 놀이기구 중 하나를 마지막으로 탄다. 이 경로를 고객경로라고 정의한다.
  • 고객은 고객경로상에 있는 모든 놀이기구를 탄다.
  • 고객은 이동하는 동안 이미 탄 적이 있는 놀이기구에 도착해도 그 놀이기구를 탄다.
  • 고객경로의 소요시간은 이용한 놀이기구의 놀이기구 대기시간, 주행시간, 이용한 공원포탈의 소요시간의 총합이다.
  • 가능한 고객경로 중 가장 소요시간이 적은 시간을 최단소요시간이라 한다.

정우는 고객들의 편의를 위하여 최단소요시간을 더 줄이고자 아래의 기준을 설립하였다.

  • 기존에 설치되어 있던 각 공원포탈의 이동시간 $S_j$를 원하는만큼 서로 바꿀 수 있다. 바꾸지 않는 것도 가능하다.
  • 공원포탈의 이동시간 $S_j$를 서로 바꾼 후 최단소요시간의 경로는 서로 바꾸기 전 최단소요시간의 경로와 다를 수 있다.

정우를 위해 최단소요시간의 최대 감소량을 구하는 프로그램을 작성하도록 하자.

입력

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(4 \le N \le 100$; $1 \le M \le \frac{N(N-1)}{2})$

그다음 줄부터 $N$개의 줄에 걸쳐 놀이기구 정보가 주어진다. 그중 $i$번째 줄은 정수 $T_i$, $P_i$가 공백으로 구분되어 주어진다. $(1 \le i \le N$; $1 \le T_i, P_i \le 100)$

그다음 줄부터 $M$개의 줄에 걸쳐 공원포탈 정보가 주어진다. 그중 $j$번째 줄은 정수 $u_j$, $v_j$, $S_j$가 공백으로 구분되어 주어진다. $(1 \le j \le M$; $1 \le u_j, v_j \le N$; $-100 \le S_j \le 100)$

$S_j$가 $0$인 경우는 순간이동을 하는 경우이며, $S_j$가 $0$보다 작은 경우는 시간을 되돌아가는 경우이다.

출력

첫 번째 줄에 최단소요시간의 최대 감소량을 출력한다.

만약 다음 조건 중 하나를 만족한다면 첫 번째 줄에 -1을 대신 출력한다.

  • 고객경로가 존재하지 않는다.
  • 고객경로가 존재할 때 소요시간을 무한히 감소시킬 수 있다.

예제 입력 1

4 5
1 5
2 6
3 7
4 8
1 2 20
1 3 -2
2 4 11
3 2 3
3 4 -10

예제 출력 1

2

예제 입력 2

4 5
1 5
2 6
3 7
4 8
1 3 -12
2 1 -10
2 4 11
3 2 -9
3 4 -10

예제 출력 2

-1