Problem A
Assassins

Picture by Cristian V. from flickr, cc by-nd

Assassins generally lay careful plans before executing them, including planning multiple attempts to dispose of the same target, with the second attempt being a backup in case the first attempt fails, the third attempt being a secondary backup, and so on. Using their great annihilytical skills, assassins can also very accurately determine the probability that any given assassination attempt will succeed.

Given the list of planned assassination attempts for a group of assassins, what are the probabilities that each assassin is alive after all these attempts? Performing an assassination attempt requires that the assassin is still alive, so if the assassin is indisposed due to already having been assassinated, the attempt is cancelled.

Input

The first line of input contains two integers $n$ and $m$, where $n$ ($1 \le n \le 15$) is the number of assassins, and $m$ ($0 \le m \le 1000$) is the number of planned assassination attempts. The assassins are numbered from $1$ to $n$.

Then follow $m$ lines, each containing two integers $i$, $j$, and a real number $p$, indicating that assassin $i$ plans to attempt to assassinate assassin $j$ ($1 \le i, j \le n$, $j \ne i$), and that this attempt would succeed with probability $p$ ($0 \le p \le 1$, at most $6$ digits after the decimal point). The planned attempts are listed in chronological order from first to last, and no two attempts happen simultaneously.

Output

Output $n$ lines, with the $i$’th containing the probability that assassin $i$ is alive after all $m$ assassination attempts have taken place. You may assume that none of the $n$ assassins will die of any other cause than being assassinated in one of these $m$ attempts. The probababilities should be accurate to an absolute error of at most $10^{-6}$.

4 3
1 2 0.25
1 4 0.42
2 3 1.0

1
0.75
0.25
0.58

2 3
1 2 0.23
2 1 0.99
1 2 0.99

0.2377000000
0.7623770000