# 1052 : Repairing a Road

Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 11 Solved: 8## Description

You live in a small town with R bidirectional roads connecting C crossings and you want to go from crossing 1 to crossing C as soon as possible. You can visit other crossings before arriving at crossing C, but it’s not mandatory.

You have exactly one chance to ask your friend to repair exactly one
existing road, **from the time you leave crossing 1**. If
he repairs the i-th road for t units of time, the crossing time after
that would be \(v_{i}a_{i}^{-t}\) .
It’s not difficult to see that it takes v_{i} units of time to
cross that road if your friend doesn’t repair it.

You cannot start to cross the road when your friend is repairing it.

## Input

There will be at most 25 test cases. Each test case begins with two
integers C and R (2<=C<=100, 1<=R<=500). Each of the next R
lines contains two integers x_{i}, y_{i}
(1<=x_{i}, y_{i}<=C) and two positive
floating-point numbers v_{i} and a_{i}
(1<=vi<=20,1<=ai<=5), indicating that there is a
bidirectional road connecting crossing x_{i} and y_{i},
with parameters v_{i} and a_{i} (see above). Each pair
of crossings can be connected by at most one road. The input is
terminated by a test case with C=R=0, you should not process it.

## Output

For each test case, print the smallest time it takes to reach crossing C from crossing 1, rounded to 3 digits after decimal point. It’s always possible to reach crossing C from crossing 1.

## Sample

3 2 1 2 1.5 1.8 2 3 2.0 1.5 2 1 1 2 2.0 1.8 0 0

2.589 1.976

## Hint

## Author

SRbGa