Шлях до знань
Вася навчається в університеті і щодня ходить туди пішки. Місто, в якому живе Вася, можна уявити як неорієнтований граф. Вася вирішив підійти до вибору маршруту науково, тому вивчив карту міста і знайшов усі найкоротші шляхи від дому до університету. Тепер, кожного разу, коли він йде в університет або повертається назад, він обирає один з цих маршрутів, причому кожен маршрут обирається з однаковою ймовірністю.
Через кілька днів Вася зауважив, що через деякі перехрестя він проходить частіше, ніж через інші. Він вирішив підрахувати, скільки разів на день в середньому він проходить через кожне перехрестя. Оскільки він зайнятий навчанням, він попросив вас виконати це завдання.
Вхідні дані
Перший рядок вхідного файлу містить два цілі числа N і M — кількість перехресть і доріг у місті, де живе Вася.
Кожен з наступних M рядків описує одну вулицю і містить три цілі числа Ai, Bi і Li — номери перехресть, які з'єднує вулиця, і її довжину в кілометрах.
Дім Васі знаходиться біля першого перехрестя, а університет — біля N-го. Гарантується, що від дому Васі можна дістатися до університету по дорогах.
1 ≤ N ≤ 10^5
0 ≤ M ≤ 10^5
1 ≤ Ai, Bi ≤ N
1 ≤ Li ≤ 10000
Вихідні дані
Виведіть N чисел — середню кількість проходів на день через кожне перехрестя від першого до N-го. Виводьте числа з абсолютною похибкою не більше 10^−7. Не забувайте, що Вася проходить містом двічі на день — в університет і назад.