e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

0-1 BFS

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

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 4
1 2 1
2 3 2
3 4 4
4 1 3
Çıxış verilənləri #1
1.00000000
0.58333333
0.33333333