Alex studies at university and goes there every day by foot. City where Alex lives, is a nonoriented graph. Alex decided to use a scientific approach when choosing the road, so he studied the map of the city and found all the shortest routes from home to university. Now every time Alex goes to the university or back, he chooses one of the routes randomly, each choice has with equal probability. In a few days Alex noticed that he passes some crossroads more often than others. He decided to calculate how many times a day he walks by each crossroads on average. But since he is busy studying, he charged you to do that for him. \InputFile The first line of input file contains two integers: N and M --- the number of crossroads and roads in Alex’s city. Each of the following M lines corresponds to one street, and contains three integers A_i, B_i and L_i --- number of crossroads the street connects and its length in kilometers. Alex’s house is right next to the 1st crossroads, his university --- is beside the N-th. It is guaranteed that it is possible to reach university from Alex’s house by roads. 1 \textit{≤ N ≤ }10^5 0 \textit{≤ M ≤ }10^5 1 \textit{≤ Ai, Bi ≤ N} 1 \textit{≤ Li ≤ }10000 \OutputFile Print out N numbers --- the average number of passes through the crossroads from first to N-th per day. Print the result with an absolute percentage error not grater than 10 ^7. Keep in mind that Alex goes through the city twice a day --- when he goes to the university and back home.