Фермер Джон намерен заставить Бесси тренироваться больше!
Бесси сейчас пасется на ферме, которая состоит из \(n\) полей, соединенных между собой \(m\) ориентированными дорогами. Нужно потратить \(w_i\) времени, чтобы пройти по соответствующей дороге. Бесси в данный момент находится на поле \(1\) и вернется к себе домой на поле \(n\) в конце дня.
Фермер Джон планирует увеличить время прохождения по некоторым дорогам. Он может увеличить время прохождения каждой дороги на неотрицательное число, но суммарная прибавка не должна превосходить \(x_i\) для \(i\)-го плана.
Определите, какому максимальному числу может быть равна длина кратчайшего пути из \(1\) в \(n\) для каждого из \(q\) независимых планов.
Выходные данные
Для каждого плана выведите максимальную длину кратчайшего пути, которую может достичь Фермер Джон, если суммарная прибавка не превосходит \(x_i\).
Ваш ответ будет считаться верным, если абсолютная или относительная погрешность не будет превосходить \(10^{-6}\).
Формально, пусть Ваш ответ равен \(a\), а ответ жюри равен \(b\). Вас ответ засчитается тогда и только тогда, когда\(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 2
2 3 2
1 3 3
5
0
1
2
3
4
|
3.0000000000
4.0000000000
4.5000000000
5.0000000000
5.5000000000
|