Background

What is a resistor? Everyone should know. What is a circuit? You probably know as well. However, in this problem, the definition of a circuit is a bit different:

Every circuit has a positive terminal on the left and a negative terminal on the right. Specifically, circuits are defined as follows:

• A single $1\Omega$ resistor (together with its two endpoints) is a circuit. (Although a wire can be regarded as a $0\Omega$ resistor, a wire alone is not a circuit.)
• If $A$ and $B$ are both circuits, let $1,2,3$ be three nodes from left to right. Connect the positive and negative terminals of $A$ to $1$ and $2$, respectively, and those of $B$ to $2$ and $3$, respectively. Then the part from $1$ to $3$ is a circuit, with $1$ as the positive terminal and $3$ as the negative terminal.
• If $A$ and $B$ are both circuits, let $1,2,3,2',3',1'$ be six nodes, where $1$ is to the left of $2$ and $3$, $2$ is to the left of $2'$, $3$ is to the left of $3'$, and $2'$ and $3'$ are to the left of $1'$. There are wires between $1$ and $2$, between $1$ and $3$, between $2'$ and $1'$, and between $3'$ and $1'$. Connect the positive and negative terminals of $A$ to $2$ and $2'$, respectively, and those of $B$ to $3$ and $3'$, respectively. Then the part from $1$ to $1'$ is a circuit, with $1$ as the positive terminal and $1'$ as the negative terminal.

Now you are given a circuit. Find the resistance between its positive and negative terminals.

Problem 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