Məsələlər
Плохие дороги
Плохие дороги
В некоторой стране есть несколько городов, соединенных дорогами. В связи с недостатком бюджета, на многих дорогах находятся выбоины, поэтому не любая машина может проехать по каждой дороге. Также некоторые дороги построены на частные средства, поэтому для проезда по этой дороге необходимо заплатить пошлину. Все пошлины стандартизированы и равны одной условной единице. Про каждую дорогу известно время, необходимое, чтобы по ней проехать.
Вам необходимо добраться из города \textbf{s} в город \textbf{t} не более чем за \textbf{maxtime} минут. При этом у Вас есть \textbf{money }условных единиц.
Вам необходимо выбрать автомобиль такой минимальной высоты, чтобы он мог проехать, невзирая на выбоины (для этого высота автомобиля должна быть не менее глубины выбоин).
\InputFile
В первой строке входного файла находится число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) - количество городов, \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^4}) - количество дорог, \textbf{s} - начальный город и \textbf{t} - конечный город. Во второй строке находится \textbf{money} (\textbf{0} ≤ \textbf{money} ≤ \textbf{10^6}) и \textbf{maxtime} (\textbf{0} ≤ \textbf{maxtime} ≤ \textbf{10^6}). В последующих \textbf{m} строках для каждой дороги находится пять чисел: начальный город, конечный город, признак пошлины (\textbf{1} - есть, \textbf{0} - нет), время в пути \textbf{time} (\textbf{0} ≤ \textbf{time} ≤ \textbf{10^4}) и глубина выбоин \textbf{deep} (\textbf{0} ≤ \textbf{deep} ≤ \textbf{10^6}).
\OutputFile
Если добраться из \textbf{s} в \textbf{t} с заданными ограничениями невозможно, выведите "\textbf{-1}". Иначе в первую строку выведите минимальную высоту автомобиля, во вторую - количество ребер в выбранном Вами пути, в третью - номера ребер в пути (ребра нумеруются с единицы в порядке их перечисления во входном файле).
Giriş verilənləri #1
2 2 1 2 1 100 1 2 1 100 77 1 2 1 100 66
Çıxış verilənləri #1
66 1 2