Вася учится в университете и каждый день ходит туда пешком. Город, в котором живёт Вася, представляет собой неориентированный граф. Вася решил использовать научный подход в выборе дороги, поэтому он изучил карту города и нашёл все кратчайшие маршруты от дома до университета. Теперь каждый раз, когда Вася идёт в университет или обратно, он выбирает один из маршрутов, причём каждый маршрут выбирается с равной вероятностью. Через несколько дней Вася заметил, что через некоторые перекрёстки он ходит чаще, чем через другие. Он решил посчитать, сколько раз в день он в среднем проходит через каждый перекрёсток. Но, поскольку он занят учёбой, он поручил это сделать вам. \InputFile Первая строка входного файла содержит два целых числа \textit{N }и \textit{M }--- количество перекрёстков и дорог в городе, где живёт Вася. Каждая из следующих \textit{M }строк соответствует одной улице и содержит три целых числа \textit{Ai}, \textit{Bi }и \textit{Li }--- номера перекрёстков, которые соединяет улица, и её длину в километрах. Дом Васи находится рядом с первым перекрёстком, а университет --- рядом с \textit{N }-м. Гарантируется, что от дома Васи можно дойти до университета по дорогам. 1 \textit{≤ N ≤ }10^5 0 \textit{≤ M ≤ }10^5 1 \textit{≤ Ai, Bi ≤ N} 1 \textit{≤ Li ≤ }10000 \OutputFile Выведите \textit{N }чисел --- среднее количество проходов в день через перекрёстки с первого по \textit{N }-й. Выводите числа с абсолютной погрешностью не более 10^\{−7\}. Не забывайте, что Вася проходит по городу два раза в день --- в университет и обратно.