Problem Description

The goal of this problem is to find the bridges in an infinite undirected graph.

This undirected graph has the following properties:

1. The graph is connected.

2. All nodes are divided into several layers, namely the 1st layer, 2nd layer, 3rd layer, and so on, with an infinite number of layers, each containing \( n \) nodes. For convenience, we denote the \( x \)-th node in the \( i \)-th layer as \( (i, x) \).

3. Nodes within the same layer can be connected by edges, and nodes between adjacent layers can also be connected by edges. No other connections between nodes are allowed.

4. If there is an edge with weight \( d \) between \( (i, x) \) and \( (i, y) \), then there is also an edge between \( (j, x) \) and \( (j, y) \) with weight \( 0.9^{j-i}d \), where \( j \) is any positive integer.

5. If there is an edge with weight \( d \) between \( (i, x) \) and \( (i+1, y) \), then there is also an edge between \( (j, x) \) and \( (j+1, y) \) with weight \( 0.9^{j-i}d \), where \( j \) is any positive integer. An undirected graph as described above satisfies all these properties.

An infinite undirected graph is connected if and only if there exists a path connecting any two nodes in the graph. An edge is a bridge if and only if removing that edge disconnects the graph.

Please write a program to read this infinite connected graph and find the sum of the weights of all bridges. For example, in the graph above, the bold edges are the only bridges, so the sum of the weights of the bridges in the graph is \( 1 \).

Input Format

The first line of the input file infinite.in contains three non-negative numbers \( n \), \( m_1 \), and \( m_2 \), separated by spaces. From the 2nd line to the \( m_1 + 1 \)-th line, each line contains three positive integers \( x \), \( y \), and \( d \), indicating an edge with weight \( d \) between \( (1, x) \) and \( (1, y) \).

From the \( m_1 + 2 \)-th line to the \( m_1 + m_2 + 1 \)-th line, each line contains three positive integers \( x \), \( y \), and \( d \), indicating an edge with weight \( d \) between \( (1, x) \) and \( (2, y) \). Each line's three integers are separated by a space.

There may be more than one edge between two nodes \( x \) and \( y \), and an edge may connect a node to itself.

Output Format

The output file infinite.out contains only one line with a real number, which is the sum of the weights of all bridges, rounded to two decimal places.

Sample Input and Output

Sample Input #1

3 1 3
1 2 4
1 2 5
2 3 3
3 3 1

Sample Output #1

1.00

Sample Input #2

1 1 1
1 1 100
1 1 1

Sample Output #2

10.00

Notes

Sample Explanation 1

This is the example given in the problem description.

Data Size

For 100% of the data, \( d \leq 100 \).

见题面 Input 部分

见题面 Output 部分