Description

Cjwssb recently encountered a tough problem in physics. He does not know how to compute the equivalent resistance of a circuit. He turned to you for help.

This circuit satisfies the following constraints:

1. The circuit consists only of wires and resistors of $1\Omega$.
2. The circuit is connected from left to right, that is, for every resistor or wire with endpoints $x,y$, it holds that $x<y$.
3. Node $1$ is the positive terminal of the power supply, and node $n$ is the negative terminal.
4. Each node is either unused, or serves as the junction of exactly two branch subcircuits that are connected either in series or in parallel.

Input Format

The first line contains two positive integers $n,m$, the numbers of nodes and resistors. Nodes are numbered from left to right, so a smaller index is to the left of a larger index.

Each of the next $m$ lines contains three integers $a_i,b_i,c_i$, meaning there is a resistor between nodes $a_i$ and $b_i$ with resistance $c_i$, where $c_i$ is either $0$ or $1$, and for every $i$ it is guaranteed that $a_i<b_i$.

Output Format

Output a real number, the total resistance, rounded to three decimal places.

7 7
1 2 0
1 3 0
2 4 1
3 5 1
4 6 0
5 6 0
6 7 1

1.500

Hint

[Sample Explanation]

Draw the diagram and the answer is obvious.

[Constraints]

P.S. The testdata are randomly generated under a fixed $n$, and the answer is guaranteed not to exceed 10 000.

By: saffah.

Translated by ChatGPT 5