Bridge Sum in an Infinite Layered Graph

We are given an infinite undirected graph whose nodes are arranged in infinitely many layers. Each layer $i$ ($i\ge1$) contains $n$ nodes numbered from $1$ to $n$, denoted as $(i, x)$ for $1 \le x \le n$. The graph is constructed according to the following rules:

1. The graph is connected.

2. There are two types of edges, and all edges are undirected. In each layer, some pairs of nodes are connected. Moreover, some nodes in consecutive layers are connected.

3. For every edge between two nodes in the same layer, say an edge of weight $d$ connecting $(i,x)$ and $(i,y)$, the following property holds: for every positive integer $j\ge i$, there is an edge between $(j,x)$ and $(j,y)$ with weight $0.9^{j-i} \cdot d$.

4. For every edge between two consecutive layers, say an edge of weight $d$ connecting $(i,x)$ and $(i+1,y)$, for every positive integer $j\ge i$, there is an edge connecting $(j,x)$ and $(j+1,y)$ with weight $0.9^{j-i} \cdot d$.

A (base) edge (i.e. the family generated by a single input edge) is called a bridge if, after removing all of its copies from the graph, the entire infinite graph becomes disconnected. Notice that if a base edge with original weight $d$ is a bridge, then its copies appear in every applicable layer and their total weight forms a geometric series with sum [ \frac{d}{1-0.9} = 10,d. ]

Your task is to determine the sum of weights of all bridges in the infinite graph given the finite blueprint. It is guaranteed that the infinite graph generated by the blueprint is connected.

The input is given as follows. The first line contains three integers:

• $n$: the number of nodes in each layer,
• $m_1$: the number of intra-layer edges (edges within each layer), and
• $m_2$: the number of inter-layer edges (edges between layer $i$ and layer $i+1$).

Then follow $m_1$ lines, each containing three numbers $u$, $v$, $d$ (with $1\le u,v\le n$) describing an intra-layer edge in the first layer having weight $d$. For each such edge, for every layer $i\ge1$ there is an edge between $(i, u)$ and $(i, v)$ with weight $0.9^{i-1}d$.

Then follow $m_2$ lines, each containing three numbers $x$, $y$, $d$ (with $1\le x,y\le n$) describing an inter-layer edge between layer $i$ and layer $i+1$ in the blueprint (for $i=1$); for every $i\ge1$, there is an edge between $(i, x)$ and $(i+1, y)$ with weight $0.9^{i-1}d$.

A base edge (either intra- or inter-layer) is a bridge if after removing all of its copies from the infinite graph the graph becomes disconnected. In this problem, to decide whether a base edge is a bridge, you can work with a finite mosaic graph constructed from two consecutive layers as follows:

Construct a graph with vertices $1,2,\dots, n$ representing layer 1 and vertices $n+1, n+2,\dots,2n$ representing layer 2. For each intra-layer edge in the blueprint (given with weight $d$), add an edge connecting $u$ and $v$ in layer 1 with weight $d$, and another edge connecting $n+u$ and $n+v$ in layer 2 with weight $0.9d$. For each inter-layer edge (with weight $d$), add an edge connecting vertex $x$ in layer 1 and vertex $n+y$ in layer 2 with weight $d$.

A base edge is a bridge if, when you remove all its copies (i.e. for an intra-layer edge remove both copies; for an inter-layer edge remove its single copy from the mosaic), the mosaic graph becomes disconnected. The contribution of a bridge is then $10d$ (because of the infinite geometric series).

Output the sum of the weights of all bridges in the infinite graph. For example, if the only bridge has an original weight $0.1$, its total contribution will be $1$, and you should output 1.

inputFormat

The first line contains three integers $n$, $m_1$, $m_2$.

Following this, there are $m_1$ lines; each line contains two integers $u$ and $v$ and a real number $d$ describing an intra-layer edge in the first layer.

Then there are $m_2$ lines; each line contains two integers $x$ and $y$ and a real number $d$ describing an inter-layer edge (from layer $i$ to layer $i+1$ in the blueprint).

It is guaranteed that $1\le u,v,x,y\le n$.

outputFormat

Output a single number, which is the sum of the weights of all bridges in the infinite graph. The answer will be accepted if it is correct within a reasonable error tolerance.

sample

2 1 1
1 2 1
1 1 1

20.0