eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Граф 1, 1/2, 1/3, 1/4

Граф 1, 1/2, 1/3, 1/4

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дан связный, взвешенный неориентированный граф, ребра которого имеют веса 1, 1/2, 1/3, 1/4. Найдите кратчайший путь от вершины 1 до всех остальных.

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

В первой строке записаны два натуральных числа n и m (1n10^6, 1m8 *10^5) - количество вершин и ребер графа соответственно. Далее записаны ребра на отдельных строках. Ребра задаются тремя натуральными числами: u, v и w (1u, vn, uv, 1w4), которые обозначают наличие ребра из u в v веса 1/w.

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

Для каждой вершины от 2 до n выведите одно число - длину кратчайшего пути от вершины 1 до нее, с точностью не менее 8 знаков после запятой.

prb5471.gif

Пример

Входные данные #1
4 4
1 2 1
2 3 2
3 4 4
4 1 3
Выходные данные #1
1.00000000
0.58333333
0.33333333