배구

# 제목 설명

Petya는 배구를 아주 좋아합니다.어느 날, 그는 서둘러 배구 시합에 참가하러 갔다.Petya는 아직 자신의 차를 사지 않았기 때문에 택시를 타야 했습니다.이 도시에는 $n$개의 길목이 있는데, 그 중 일부 길목은 양방향 도로를 통해 연결되어 있다.각 도로의 길이는 양의 정수 (m) 로 정의되며 길이는 다를 수 있습니다.

처음에는 길목마다 택시가 한 대씩 서 있었다.$i$번째 길목에서 온 택시 기사는 주행 거리가 $t _ {i}$m를 넘지 않는 한 Petya (가장 많은 중간 길목을 지나갈 수 있음) 를 다른 길목으로 차로 배웅하는 데 동의했습니다.또한 승차료는 거리와 상관없이 $c_{i}$루블과 같습니다.택시는 도로 중간에 주차할 수 없습니다.택시 한 대당 최대 한 번만 이용할 수 있다.Petya는 택시가 처음 정차하는 길목에서만 승차할 수 있습니다.

이제 Petya는 길목 $x$에 있고 배구장은 길목 $y$에 있습니다.Petya가 경기장에 도착하는 데 필요한 최소 금액을 결정합니다.

# 형식 입력

첫 번째 행에는 두 개의 정수 $n$와 $m$($1<=n<=1000, 0<=m<=1000$)가 포함됩니다.그것들은 각각 도시의 길목 수와 도로 수이다.길목은 $1$에서 $n$까지 번호가 매겨지며 $n$를 포함합니다.다음 행에는 두 개의 정수 $x$와 $y$($1<=x, y<=n$)가 있습니다. 각각 시작 및 끝 길목의 번호입니다.다음 $m$행에는 도로에 대한 설명이 포함되어 있습니다.각 라우팅의 정수 $u _ {i}$, $v _ {i}$, $w _ {i}$($1 < = u _ {i}, v _ {i} < =n, 1 < = w _ {i} < = 10^ {9} $) 설명은 각각 도로 연결의 길목 번호와 도로 길이입니다.다음 $n$행에는 $n$쌍 정수 $t_{i}$와 $c_{i}$($1<=t_{i}, c_{i}<=10^{9}$)가 포함되어 있으며, $i$길목에서 대기 중인 택시 운전사 - 그가 가장 많이 달릴 수 있는 거리와 승차 요금을 설명합니다.도로는 길목을 자체로 연결할 수 없지만 한 쌍의 길목 사이에 여러 개의 도로가 있을 수 있다.각 행의 연속 숫자는 적절한 공백 문자로 구분됩니다.

# 출력 형식

택시가 목적지까지 Petya를 보낼 수 없는 경우 "-1"을 인쇄합니다(따옴표 없음).그렇지 않으면 승차 최소 요금을 인쇄합니다.

C++에서 64비트 정수를 읽거나 쓸 때%lld 설명자를 사용하지 마십시오.cin, cout 흐름 또는%I64d 설명자를 사용하는 것이 좋습니다.

4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7

9

# 힌트

최적 노선 - 길목에서 1부터 2까지 (길목을 지나 4), 그리고 2부터 3까지.비용은 7 + 2 = 9 루블입니다.