Задачі
Граф 1, 1/2, 1/3, 1/4
Граф 1, 1/2, 1/3, 1/4
Задано звязний, зважшений неорієнтовний граф, ребра якого мають ваги 1, 1/2, 1/3, 1/4. Знайдіть найкоротший шлях від вершини 1 до усіх інших.
Вхідні дані
У першому рядку записано два натуральних числа n та m (1 ≤ n ≤ 106
, 1 ≤ m ≤ 8 *105
) - кількість вершин та ребер графа відповідно. Далі записані ребра у окремих рядках. Ребра задаються трьома натуральними числами: u, v та w (1 ≤ u, v ≤ n, u ≤ v, 1 ≤ w ≤ 4), які позначають наявність ребра із u в v вагою 1/w.
Вихідні дані
Для кожної вершини від 2 до n виведіть одне число - довжину найкоротшого шляху від вершини 1 до неї, з точністю не менше 8 знаків після коми.
Вхідні дані #1
4 4 1 2 1 2 3 2 3 4 4 4 1 3
Вихідні дані #1
1.00000000 0.58333333 0.33333333