Плохие дороги
В некоторой стране есть несколько городов, соединенных дорогами. В связи с недостатком бюджета, на многих дорогах находятся выбоины, поэтому не любая машина может проехать по каждой дороге. Также некоторые дороги построены на частные средства, поэтому для проезда по этой дороге необходимо заплатить пошлину. Все пошлины стандартизированы и равны одной условной единице. Про каждую дорогу известно время, необходимое, чтобы по ней проехать.
Вам необходимо добраться из города s в город t не более чем за maxtime минут. При этом у Вас есть money условных единиц.
Вам необходимо выбрать автомобиль такой минимальной высоты, чтобы он мог проехать, невзирая на выбоины (для этого высота автомобиля должна быть не менее глубины выбоин).
Входные данные
В первой строке входного файла находится число n (1 ≤ n ≤ 100) - количество городов, m (1 ≤ m ≤ 10^4) - количество дорог, s - начальный город и t - конечный город. Во второй строке находится money (0 ≤ money ≤ 10^6) и maxtime (0 ≤ maxtime ≤ 10^6). В последующих m строках для каждой дороги находится пять чисел: начальный город, конечный город, признак пошлины (1 - есть, 0 - нет), время в пути time (0 ≤ time ≤ 10^4) и глубина выбоин deep (0 ≤ deep ≤ 10^6).
Выходные данные
Если добраться из s в t с заданными ограничениями невозможно, выведите "-1". Иначе в первую строку выведите минимальную высоту автомобиля, во вторую - количество ребер в выбранном Вами пути, в третью - номера ребер в пути (ребра нумеруются с единицы в порядке их перечисления во входном файле).