In ICPCCamp, there are n cities and m unidirectional roads between cities.
The i-th road goes from the -th city to the -th city.
For each pair of cities u and v, there is at most one road from u to v.
As traffic in ICPCCamp is becoming heavier, toll of the roads also varies.
At time t, one should pay dollars to travel along the i-th road.
Bobo living in the 1-st city would like to go to the n-th city.
He wants to know the average money he must spend at least if he starts from city 1 at .
Note that since Bobo's car is super-fast, traveling on the roads costs him **no time**.
Formally, if f(t) is the minimum money he should pay from city 1 to city n at time t,
Bobo would like to find

The input contains at most 30 sets. For each set:
The first line contains 3 integers n, m, T ().
The i-th of the following m lines contains 4 integers 
().
It is guaranteed that Bobo is able to drive from city 1 to city n.

A floating number denotes the answer.
It will be considered correct if its absolute or relative error does not exceed .

3 3 2
1 2 1 0
2 3 1 0
1 3 1 1

1.75000000

3 3 2
1 2 1 0
2 3 1 0
1 3 0 5

2.00000000