e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.

Граф 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 знаків після коми.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 4
1 2 1
2 3 2
3 4 4
4 1 3
Вихідні дані #1
1.00000000
0.58333333
0.33333333