배구

Petya는 배구를 매우 좋아한다. 어느 날 그는 배구 경기에 늦고 있었다. Petya는 아직 자신의 자동차를 사지 않았기 때문에 택시를 타야 했다. 도시에는 n개의 교차로가 있으며, 그중 일부는 양방향 도로로 연결되어 있다. 각 도로의 길이는 미터 단위의 양의 정수로 정의되며, 도로마다 길이가 다를 수 있다.

처음에는 각 교차로에 정확히 택시 한 대가 서 있다. i-th 교차로의 택시 기사는 이동 거리가 ti미터 이하라면 Petya를 (여러 중간 교차로를 거칠 수도 있다) 다른 어떤 교차로까지 태워 주는 데 동의한다. 또한 요금은 거리에 상관없이 ci부를이다. 택시는 도로 중간에 멈출 수 없다. 각 택시는 최대 한 번만 이용할 수 있다. Petya는 택시가 처음 서 있던 교차로에서만 그 택시를 탈 수 있다.

현재 Petya는 교차로 x에 있고, 배구 경기장은 교차로 y에 있다. Petya가 경기장까지 이동하는 데 필요한 최소 금액을 구하라.

첫째 줄에는 두 정수 n와 m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000)이 주어진다. 이들은 각각 도시의 교차로 수와 도로 수이다. 교차로에는 1부터 n까지의 번호가 붙어 있다. 다음 줄에는 두 정수 x와 y (1 ≤ x, y ≤ n)이 주어진다. 이들은 각각 출발 교차로와 도착 교차로의 번호이다. 다음 m개 줄에는 도로에 대한 설명이 주어진다. 각 도로는 세 정수 ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109)으로 설명되며, 이들은 각각 도로로 연결된 교차로들의 번호와 도로의 길이이다. 다음 n개 줄에는 n쌍의 정수 ti와 ci (1 ≤ ti, ci ≤ 109)이 주어진다. 이는 i-th 교차로에서 기다리는 택시 기사를 설명하며, 각각 그 기사가 운전할 수 있는 최대 거리와 운행 요금이다. 도로는 하나의 교차로를 자기 자신과 연결할 수 없지만, 한 쌍의 교차로 사이에는 도로가 여러 개 있을 수 있다. 각 줄에서 연속한 모든 수는 정확히 하나의 공백 문자로 구분된다.

택시들을 이용해 Petya를 목적지까지 데려갈 수 없다면 "-1"을 따옴표 없이 출력한다. 그렇지 않으면 이동의 최소 비용을 출력한다.

С++에서 64비트 정수를 읽거나 쓸 때 %lld 지정자를 사용하지 말라. cin, cout 스트림 또는 %I64d 지정자를 사용하는 것이 권장된다.

최적의 방법은 교차로 1에서 2까지 (교차로 4를 거쳐) 이동한 다음, 2에서 3까지 이동하는 것이다. 비용은 7+2=9부를이다.