Problem B
Dangerous 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}$.

2 1
0 1 0.5

0.500000000 1.000000000

2 1
0 1 0.25

0.750000000 1.000000000