Dangerous Skiing

/problems/dangerousskiing/file/statement/en/img-0001.jpg
Lukáš loves skiing. One morning, the sun was shining like no other sun had ever shone before, and he wanted to do something exciting. There had been a slight storm during the night, and the wind had cleared snow from certain parts of the mountain, making them icy and more dangerous to ski down. Lukáš was aware of this, but brave as he (mostly) is, he decided that he would climb his favourite mountain and go for some really exciting skiing.

Lukáš starts at the top of the mountain, and wants to get to the bottom. There are $N$ small cabins scattered along the mountainside, numbered $0$ to $N-1$. He will always go from one cabin to another, along certain pistes. For each piste, which always connects exactly two cabins, he has calculated the probability of falling along that piste. The cabin numbered $0$ is located at the top, and the cabin numbered $N-1$ is located at the bottom of the mountain.

If Lukáš feels like it, he can take his skis off and walk down a piste instead. By doing this, it is guaranteed that he will not fall along this piste in the direction that he walks. But taking the skis off is not very brave…

Lukáš can only ski down the mountain, i.e. from a lower numbered cabin to a higher numbered one, but he can walk along any piste in any direction. It is guaranteed that Lukáš can walk from the top of the mountain to the bottom of it.

Your task is to help Lukáš predict his chances of getting down the hill without falling. For each number $k \in [0,N-1]$ you should calculate the maximum probability that Lukáš gets down the hill without falling, while walking along at most $k$ pistes, and assuming he choses his walking wisely.

Input

The first line contains two integers $1 \le N \le 300$ and $0 \le M \le \frac{N(N-1)}{2}$, the number of cabins and pistes respectively.

Then follow $M$ lines, each describing a piste with three numbers $0 \le a, b < N$ and $0 \le w \le 1$, where $a$ and $b$ are the numbers of the cabins the piste connects, and $w$ is the probability that Lukáš will fall while skiing down the piste.

Output

Output should consist of $N$ floating point numbers $p_ k$ ($k \in [0,N-1]$), each denoting the maximum probability that Lukáš didn’t fall when walking along at most $k$ pistes. If it is impossible to get down the hill by walking along at most $k$ pistes, then output $p_ k=-1$. Output them on a single line separated by spaces. Your answer is considered correct if the relative or absolute error is at most $10^{-9}$.

Sample Input 1 Sample Output 1
2 1
0 1 0.5
0.500000000 1.000000000
Sample Input 2 Sample Output 2
2 1
0 1 0.25
0.750000000 1.000000000