Probability of a Spanning Tree After a Flood

T country has \(N\) cities which are connected by several bidirectional roads; between any two cities there is at most one road. Recently, after a flood, some roads were damaged and became impassable. Although an investigation into the damage has begun, almost no information has been transmitted so far.

The government, however, had previously measured the strength of every road. For each road, you are given the probability that it remains passable after the flood. Using only this statistical information, you are to compute the probability that exactly \(N-1\) roads are passable and, as a consequence, the \(N\) cities are connected (i.e. the passable roads form a spanning tree).

Formally, suppose the country has \(M\) roads. For the \(i\)-th road with probability \(p_i\) of remaining passable, the event that it is passable occurs independently. Let \(S\) be a subset of roads. Then the probability that exactly the roads in \(S\) are passable is \[ \prod_{e\in S} p_e\prod_{e\notin S}(1-p_e). \] We want the sum of these probabilities over all subsets \(S\) of size \(N-1\) which also connect all cities. Equivalently, if we denote by \(\mathcal{T}\n\) the collection of all spanning trees of the graph, the answer is \[ \sum_{T\in \mathcal{T}} \left(\prod_{e\in T} p_e\prod_{e\notin T}(1-p_e)\right). \]

An efficient way to compute this is to note that if none of the roads has \(p_i=1\), then we can factor out \(\prod_{i=1}^{M}(1-p_i)\) to obtain \[ \prod_{i=1}^{M}(1-p_i)\cdot\sum_{T\in \mathcal{T}} \prod_{e\in T}\frac{p_e}{1-p_e}, \] and the sum over spanning trees can be computed by the Matrix Tree Theorem. However, special care must be taken when some \(p_i=1\) (i.e. the road is forced to remain), as these edges must appear and must not create a cycle. In our solution we first contract all forced edges and then use the Matrix Tree Theorem on the contracted graph with weights \(r_e=\frac{p_e}{1-p_e}\) for the remaining (non-forced) edges. Finally, we multiply by the factor \[ \prod_{e:\; p_e<1}(1-p_e). \]

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \leq N \leq 100\), \(0 \leq M \leq \frac{N(N-1)}{2}\)), representing the number of cities and the number of roads respectively. Each of the following \(M\) lines contains two integers \(u\) and \(v\) (\(1 \leq u,v \leq N,\; u\neq v\)) and a real number \(p\) (\(0 \le p \le 1\)), indicating that there is a road connecting cities \(u\) and \(v\) with a passable probability of \(p\). It is guaranteed that there is at most one road between any two cities.

outputFormat

Output a single real number, the probability that exactly \(N-1\) roads are passable and they connect all cities. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 3
1 2 0.5
2 3 0.5
1 3 0.5

0.375