Задача Светофоры

Описание

В городе есть N перекрестков, пронумерованных числами от 1 до N. Некоторые перекрестки соединены дорогами. Машина выехала из пункта А (перекрестка) в пункт B (перекресток). Изначально, как только машина тронулась с места - все светофоры горят зеленым светом. На каждом перекрестке светофор Si горит Xi секунд зеленым, Yi секунд красным светом. Если машина подъезжает к перекрестку, где на светофоре горит красный свет, то он ждет, пока не загорится зеленый. Напишите программу, которая посчитает минимальное время, за которое машина может проехать из пункта A в пункт B.

Формат входных данных

Во входном файла сначала записаны три числа: N, M, K – количество перекрестков в городе, количество дорог, скорость машины в м/сек (1<=N<=1000, 1<=M<=15000, 1<=K<= 10000). N, M – целые числа, K – дробное.

Далее следуют M троек чисел Ui, Vi, Ti, описывающие дороги: Ui и Vi номера перекрестков, которая соединяет данная дорога длиною Ti метров (1<=Ti<=1000000). Считает, что если есть путь из перекрестка U в перекресток V, то существует путь из V в U.

Далее следуют N пар чисел Xi, Yi, описывающие светофоры на перекрестках: Xi – сколько горит зеленый свет, Yi – сколько горит красный свет на данном перекрестке (1<=Xi<=10000, 1<=Yi<=10000). Далее идут два числа A и B – номера перекрестков, из которой выехала машина и в которую должна добраться за минимальное время.

Формат выходных данных

Выведите в выходной файл одно число – минимальное время, за которое машина может добраться из пункта A до пункта B с точностью до четырех знаков после запятой (округлить до четырех знаков после запятой). Если такого пути не существует, то выведите -1.

Примечание: если правильный ответ 3.4444 , то нельзя выдавать ответы 3.444444, 3.44 и т.п., надо выводить с точностью до четырех знаков после запятой.