문제
농부 창호는 소들이 비에 젖는 걸 너무나도 싫어해서, 농장에 언제 비가 오는지 알려주는 사이렌을 설치했다.
소들은 비가 오기 전에 대피 작전을 세워서 한 마리의 소도 빠짐 없이 모두 헛간 안으로 대피하려고 한다.
하지만 불행하게도 일기예보가 자주 틀려서 난감한 일이 발생되곤 한다.
비가 오지도 않는데 사이렌을 울리는 일을 최대한 줄이고, 소들이 대피할 시간을 미리 충분히 파악하여 가능한 한 사이렌을 늦게 울리려고 한다.
농장에는 N개의 목초지가 있고 목초지에는 소들이 대피할 수 있는 헛간이 세워진 곳도 있다.
헛간은 크기가 제한되어 있어서 한 헛간에 모든 소들이 들어가지 못할 수도 있으며 목초지에서 헛간으로 들어가거나 나오는 데에는 시간이 걸리지 않는다.
목초지 사이에는 소들이 이동할 수 있는 M개의 길이 있고 그 길들은 매우 넓어서 아무리 많은 소들도 한꺼번에 마음껏 양방향으로 이동할 수 있다.
창호를 위해 모든 소들이 헛간으로 대피할 때까지 걸리는 최소 시간을 구하는 프로그램을 작성해 주자.
입력
첫 줄에 N(1≤N≤200)와 M(1≤M≤1500)가 주어진다.
이후 N개의 줄에는 각 목초지의 상태를 나타내는 두 개의 정수가 입력된다. 첫 번째 수는 현재 목초지에 있는 소들의 수(0 이상 1000 이하)이며, 두 번째 수는 그 목초지에 설치된 헛간 안에 들어갈 수 있는 소의 최대 수(0 이상 1000 이하)이다. 만약 이 수가 0이라면 헛간이 없다는 것을 의미한다. 목초지의 번호는 입력되는 순서대로 1부터 N까지 매겨진다.
다음부터 M개의 줄에는 길의 정보를 나타내는 세 개의 정수 s, e, dis 가 입력된다. s와 e는 (1 ≤ s, e ≤ N)는 목초지의 번호를 나타내며, dis는(1 ≤ dis ≤ 10억) 목초지 s에서 목초지 e로 이동하는데 걸리는 시간을 의미한다. 모든 길은 양방향으로 이동이 가능하며 동일한 입력이 있을 때에는 유리한 것으로 적용한다.
출력
모든 소들이 헛간으로 대피할 때까지 걸리는 최소 시간을 출력한다. 만일 모든 소들이 대피할 수 있는 방법이 없다면 -1을 출력한다.
예제1
입력
34
72
04
26
1240
3270
2390
13120
출력
110
힌트
출처
USACO 2005 March Gold