문제
개미 마을에는 개미들이 여러 작업장에 나뉘어서 겨울을 나기 위한 먹이를 구하기 위해 열심히 일을 하고 있다. 그런데 이 개미 마을에는 무서운 개미핡기가 갑자기 나타나 개미들을 공격하기 때문에 각 작업장마다 대피소를 만들고 개미핡기가 나타나면 전체 작업장에 즉시 대피를 지시할 수 있도록 방송시스템을 갖추어 놓았다. 각 작업장에서 해당 작업장에 있는 대피소로는 즉시 이동할 수 있기 때문에 시간이 걸리지 않는다.
하지만 각 작업장마다 지형이 다르기 때문에 대피소를 충분히 크게 만들 수 없고 어떤 작업장은 아예 대피소를 만들 수 없는 곳도 있다. 따라서 개미들은 경우에 따라서는 주변의 다른 작업장의 대피소로 대피해야 한다.
각 작업장 사이에는 개미들이 이동할 수 있는 길이 있고 그 길에는 아무리 많은 개미도 충분히 동시에 이동을 할 수 있다. 여왕개미는 지금 즉시 대피명령을 내렸을 때 현재 각 작업장에서 일하고 있는 모든 개미들이 대피하는데 최소한 얼마의 시간이 걸리는지 알고 싶어 한다.
여왕 개미를 위해 모든 개미들이 대피하기 위한 최소 시간을 구하는 프로그램을 작성해 주도록 하자.
입력
첫 줄에 작업장의 수N(1 <= N <= 200)과 작업장을 잇는 길의 수 M(1 <= M <= 1500)이 주어진다.
작업장의 번호는 1번부터 N번까지이고 이후 N개의 줄에는 1번 작업장부터 N번 작업장까지 각 작업장에서 작업하고 있는 개미의 수와 대피소의 크기가 차례대로 입력된다.
대피소의 크기는 대피할 수 있는 개미의 마리수를 나타낸다. (개미의 수와 대피소의 크기는 각각 0이상 1000이하이고 0은 대피소가 없다는 의미가 된다.)
다음부터 M개의 줄에는 각각 세 개의 정수 s, e, t가 입력되는데 s작업장에서 e작업장으로 이동하는데 t시간이 걸린다는 의미이다. (1 <= s, e <= N, 1 <= t <= 10억) (입력의 20%는 N과 M이 각각 20 이하이다.)
출력
모든 개미들이 대피소로 대피할 때까지 걸리는 최소 시간을 출력한다.
만일 모든 개미들이 대피할 수 있는 방법이 없다면 -1을 출력한다.
예제
3 4
6 2
1 4
2 4
1 2 30
2 3 60
1 3 100
3 1 50
60
로그인해야 코드를 작성할 수 있어요.