배구

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-bit 정수를 읽거나 쓸 때 %lld 서식 지정자를 사용하지 말아야 한다. cin, cout 스트림 또는 %I64d 서식 지정자를 사용하는 것이 좋다.

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