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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

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

Примечания:

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

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

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

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

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

В третьей строке вводится количество безопасных переходов между различными соседними системами M. Остальные M строк содержат описания переходов в виде трех целых чисел ai, bi, li, где ai и bi - номера систем, а li - расстояние между системами в световых годах 1 ≤ li ≤ 109.

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

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

Ограничения

1 ≤ ai,bi ≤ N

1 ≤ i ≤ M

2 ≤ N ≤ 50

1 ≤ S, F ≤ N

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

1 ≤ li ≤ 109

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

Стандартный вход Стандартный выход
1
7
5 1 5
5
2 1 9
2 3 7
1 4 2
2 3 13
3 5 4
15.2915026221292
2
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

0.070s 0.009s 13