G. Корова и тренировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фермер Джон намерен заставить Бесси тренироваться больше!

Бесси сейчас пасется на ферме, которая состоит из $$$n$$$ полей, соединенных между собой $$$m$$$ ориентированными дорогами. Нужно потратить $$$w_i$$$ времени, чтобы пройти по соответствующей дороге. Бесси в данный момент находится на поле $$$1$$$ и вернется к себе домой на поле $$$n$$$ в конце дня.

Фермер Джон планирует увеличить время прохождения по некоторым дорогам. Он может увеличить время прохождения каждой дороги на неотрицательное число, но суммарная прибавка не должна превосходить $$$x_i$$$ для $$$i$$$-го плана.

Определите, какому максимальному числу может быть равна длина кратчайшего пути из $$$1$$$ в $$$n$$$ для каждого из $$$q$$$ независимых планов.

Входные данные

В первой строке задано два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le n \cdot (n-1)$$$) — количество полей и дорог соответственно.

В каждой из следующих $$$m$$$ строк задано $$$3$$$ целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^6$$$), означающих, что есть дорога от поля $$$u_i$$$ к полю $$$v_i$$$, время прохождения которой равно $$$w_i$$$.

Гарантируется, что существует путь к полю $$$n$$$ из поля $$$1$$$. Гарантируется, что граф не содержит петель и кратных ребер. Возможно, что есть как дорога из $$$u$$$ в $$$v$$$, так и дорога из $$$v$$$ в $$$u$$$.

В следующей строке задано единственное целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество независимых планов.

В каждой из следующих $$$q$$$ строк задано по одному целому числу $$$x_i$$$ ($$$0 \le x_i \le 10^5$$$) — ограничение на суммарную прибавку.

Выходные данные

Для каждого плана выведите максимальную длину кратчайшего пути, которую может достичь Фермер Джон, если суммарная прибавка не превосходит $$$x_i$$$.

Ваш ответ будет считаться верным, если абсолютная или относительная погрешность не будет превосходить $$$10^{-6}$$$.

Формально, пусть Ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Вас ответ засчитается тогда и только тогда, когда$$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Пример
Входные данные
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