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

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

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

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

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

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

Примеры