17482번 - 놀이공원을 만들자 (Small) 채점 준비 중

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

1. 놀이공원에는 N개의 놀이기구와 M개의 공원포탈이 있다.
2. 각 놀이기구의 주행시간은 T이며, 놀이기구를 탄 후 바로 공원포탈을 이용하여 다음 놀이기구의 대기인원 중 맨 뒤로 이동할 수 있다.
3. 각 놀이기구마다 대기시간 P가 있으며, 시간이 지나도 대기시간은 동일하다.
4. 각 공원포탈을 이용하여 한 놀이기구에서 다른 놀이기구로 이동하는 시간은 각각 S이다.

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

1. 가장 작은 P의 놀이기구를 처음으로 타고, 가장 큰 P의 놀이기구를 마지막으로 타고자 한다.
2. 첫 놀이기구에서 마지막 놀이기구까지 최단소요시간 안에 이동하고자 한다.
3. 최단소요시간 안에 이동하는 동안 경로 상에 있는 모든 놀이기구를 타고자 한다.
4. 최단소요시간에는 공원포탈 이동시간과 놀이기구 주행시간, 놀이기구 대기시간이 포함된다.

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

1. 기존에 설치되어 있던 각 공원포탈의 이동시간 S를 서로 바꿀 수 있다.
2. 공원포탈의 이동시간 S를 서로 바꾼 후 최단소요시간의 경로는 서로 바꾸기 전 최단소요시간의 경로와 다를 수 있다.

정우를 위해 공원포탈의 이동시간 S를 서로 바꾸기 전의 최단소요시간과 서로 바꾼 후의 최단소요시간의 차이를 알아내는 프로그램을 작성하도록 하자.

첫 번째 줄에 N과 M이 주어진다. (4 ≤ N ≤ 100, N ≤ M ≤ N(N-1)/2) 이후 놀이기구를 R이라고 할 때, 두 번째 줄부터 N개의 줄에 걸쳐 R₁부터 R_N까지의 T와 P가 순서대로 주어지며, (N+2)번째 줄부터 M개의 줄에 걸쳐 출발지점 R_i, 도착지점 R_j와 두 지점 사이의 이동시간 S가 주어진다. (1 ≤ T ≤ P ≤ 100, 1 ≤ S ≤ 100)

공원포탈의 이동시간 S를 서로 바꾸기 전의 최단소요시간과 서로 바꾼 후의 최단소요시간의 차이를 출력한다. 만약 공원포탈의 이동시간 S를 서로 바꾸기 전 가장 작은 P의 놀이기구에서 시작하여 가장 큰 P의 놀이기구로 가는 과정에서 가장 큰 P의 놀이기구로 갈 수 있는 경로가 없다면 -1을 출력한다.