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<=v_i<=20,1<=a_i<=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.

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

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