‘How could I forget it? In T hours we must show the alphaversion of our game to a potential investor!
This meeting is crucial for us! If we miss it, we possibly won’t have a chance to complete the development.’
‘Don’t panic! Where do they wait for us?’
‘In their Tmutarakan office. Let’s go right now. I think we’ll be there in time, but we’ll have to exceed the speed limit in a couple of places.’
‘We don’t need problems with the police—we’ll lose precious time. We’ll work out a route to get to the investor in time
such that the maximal needed overspeeding along this route is as minimal as possible.’
Input
The first line contains the number n of crossroads and the number m of roads between them (2 ≤ n ≤ 10 000; 1 ≤ m ≤ 10 000).
All the roads have twoway traffic. The ith of the following m lines contains integers a_{i}, b_{i}, s_{i},
and l_{i} (1 ≤ a_{i} < b_{i} ≤ n; 1 ≤ s_{i} ≤ 300; 1 ≤ l_{i} ≤ 1 000), which mean that there is an l_{i}kilometer long road with speed limit s_{i} kilometers per hour
between crossroads a_{i} and b_{i}.
The game developers’ office is at crossroad 1, and the investor’s office is at crossroad n.
It is guaranteed that there is a way from crossroad 1 to crossroad n.
The last line contains the number T of hours left before the meeting (1 ≤ T ≤ 10^{6}).
Output
Describe a route by which the developers can get to the investor’s office in time with minimum overspeeding.
In the first line output numbers S and k, which are the minimum overspeeding in kilometers per hour
and the number of roads in the route.
In the second line output k integers separated with a space. The integers are the numbers of roads in the order in which
they must be traveled.
The roads are numbered from 1 to m in the order in which they are given in the input.
If there are several ways to get to the investor’s office with the overspeeding S,
output any of them.
The absolute or relative error of S should not exceed 10^{−6}.
Samples
input  output 

3 3
1 3 50 150
1 2 80 100
2 3 80 100
2
 20.000000 2
2 3

2 1
1 2 60 60
1
 0.000000 1
1

Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013