In a country, there is a number of cities connected by roads. Due to
insufficient budget, some roads are covered with potholes, so certain
cars cannot use certain roads. Thus each road has the height number
associated with it — that is the minimal height of the bottom of a car
that can drive through that road. On the other hand, some roads are private,
and one should pay for using them. Luckily, the amount to be paid is
standartized and equals one standard unit. Finally, for each road, the time
required to drive through it is known.
Given that you have to drive from city s to city t using no more than
maxtime minutes of time, no more than money standard units, find the
minimal height of the bottom of the car which makes it possible.
Input
The number of cities n (1 ≤ n ≤ 100), the number of roads m
(1 ≤ m ≤ 10^{4}), and the numbers of starting and ending cities s
and t (1 ≤ s, t ≤ n) are given on the first line of the input.
The second line contains money (0 ≤ money ≤ 10^{6}) and maxtime
(0 ≤ maxtime ≤ 10^{6}).
Each of the next m lines has the form u_{i} v_{i} c_{i} t_{i} h_{i}.
Here, u_{i} is the starting city for ith road, v_{i} is the ending city,
c_{i} is 1 if it is a private road and 0 otherwise, t_{i} is the time
required to drive through that road, and h_{i} is the height of the car
required to pass (1 ≤ u_{i}, v_{i} ≤ n, 0 ≤ t_{i} ≤ 10^{4} and
0 ≤ h_{i} ≤ 10^{6}). Note that the roads are unidirectional. All the
numbers in the input are integers.
Output
If there is no way to drive from s to t under given restrictions,
output "−1". Otherwise write on the first line the minimal height
of the car; the second line should contain the number of roads used to travel
from s to t; and the third line must be filled by the numbers of the roads
you used in the order of usage. Roads are numbered from 1 to m; the
order is the same as in input.
Samples
input  output 

2 2 1 2
1 100
1 2 1 100 77
1 2 1 100 66
 66
1
2

2 2 1 2
0 100
1 2 0 101 77
1 2 1 100 66
 1

Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007