Задано звязний, зважшений неорієнтовний граф, ребра якого мають ваги 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 знаків після коми.