Путь к знаниям
Вася учится в университете и каждый день ходит туда пешком. Город, в котором живёт Вася, представляет собой неориентированный граф. Вася решил использовать научный подход в выборе дороги, поэтому он изучил карту города и нашёл все кратчайшие маршруты от дома до университета. Теперь каждый раз, когда Вася идёт в университет или обратно, он выбирает один из маршрутов, причём каждый маршрут выбирается с равной вероятностью.
Через несколько дней Вася заметил, что через некоторые перекрёстки он ходит чаще, чем через другие. Он решил посчитать, сколько раз в день он в среднем проходит через каждый перекрёсток. Но, поскольку он занят учёбой, он поручил это сделать вам.
Входные данные
Первая строка входного файла содержит два целых числа 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}. Не забывайте, что Вася проходит по городу два раза в день — в университет и обратно.