Equivalent Resistance

Problem Description

You are given a circuit diagram with $n$ vertices and $m$ edges, the vertices numbered from $1$ to $n$. Vertex $1$ is the positive terminal and vertex $n$ is the negative terminal, and the circuit is guaranteed to be connected.

An edge $(i, j, c)$ means there is a circuit between vertex $i$ and vertex $j$ with a resistor of resistance $c$ in the middle; there may be multiple parallel resistor branches between two vertices.

Now answer: what is the equivalent resistance of the whole circuit from vertex $1$ to vertex $n$?

Input Format

The first line contains two positive integers $n$ and $m$, the number of vertices and edges.

The following $m$ lines each contain three integers $i, j, c$, meaning there is a path with resistance $c$ between vertex $i$ and vertex $j$.

The data guarantees that vertex $1$ and vertex $n$ are connected.

Output Format

Output one number on a line: the answer.

Your answer is accepted if its relative or absolute error from the standard answer is within $10^{-6}$.

Sample Input 1

3 3
1 2 1
1 2 1
2 3 2

Sample Output 1

2.5000000000

Sample Input 2

4 5
1 2 1
2 4 4
1 3 8
3 4 19
2 3 12

Sample Output 2

4.2098138748

Constraints

For $100\%$ of the data, $2 \leq n \leq 50, 1 \leq m \leq 2000, 1 \leq i, j \leq n, i \neq j, 1 \leq c \leq 10^4$.

Hint

Series circuit: $R = R_1 + R_2 + ... + R_n$

Parallel circuit: $1 / R = 1 / R_1 + 1 / R_2 + ... + 1 / R_n$

$I_{i,j} = U_{i,j} / R_{i,j}$

For vertices other than the two terminals, $I_{in} = I_{out}$

Equivalent resistance $R_{1, n} = U_{1, n} / I$