Задача D. Полеты в космосе ≡

Условие

Экспедиция, в которую входит лейтенант О'Денил, собирается отправиться в далекую звездную систему F из системы S. Но ограничения на количество топлива в корабле не позволяют лететь напрямую по назначению, так что приходится делать дозаправки в других системах не реже, чем через T лет. Чтобы максимально быстро преодолевать межзвездные расстояния, половину пути корабль летит равноускоренно с ускорением a = 1св.год / год², а вторую половину равнозамедленно с тем же ускорением, что позволяет останавливаться вовремя. Дозаправки, по сравнению с перелетами, происходят моментально. Кроме того, из-за космических опасностей возможны перелёты только по заданным переходам.

Необходимо определить, за какое минимальное время исследователи могут добраться до своей цели.

Примечания:

Если корабль начал движение с нулевой начальной скоростью, то расстояние, пройденное им за время t с ускорением a, следует считать по формуле at²2.

Световой год - расстояние, которое свет проходит в вакууме за один год.

Формат входных данных

В первой строке вводится целое число T – максимальное время перелета между системами в годах.

Во второй строке вводится 3 целых числа: количество известных звездных систем N, номер начальной звездной системы S и номер конечной F (S ≠ F).

В третьей строке вводится количество безопасных переходов между различными соседними системами M. Остальные M строк содержат описания переходов в виде трех целых чисел a_i, b_i, l_i, где a_i и b_i - номера систем, а l_i - расстояние между системами в световых годах 1 ≤ l_i ≤ 10⁹.

Формат выходных данных

Выведите единственное число - минимально возможное время полета в годах, с точностью не менее двух десятичных знаков.

Ограничения

1 ≤ a_i,b_i ≤ N

1 ≤ i ≤ M

2 ≤ N ≤ 50

1 ≤ S, F ≤ N

1 ≤ M ≤ N ⋅ (N − 1)2

1 ≤ l_i ≤ 10⁹

Примеры тестов

7
5 1 5
5
2 1 9
2 3 7
1 4 2
2 3 13
3 5 4

15.2915026221292

200
7 1 5
12
1 4 10403
1 5 14444
1 7 4
2 3 7609
3 4 233
3 5 3393
4 2 5278
4 5 8023
5 6 2781
6 2 3303
7 3 997
7 6 5664

183.649540649073