Kirchhoff's Laws

Time limit2sMemory limit512 MB

Summary

Given a resistor network, compute the equivalent resistance between node 1 and node N by solving Kirchhoff's laws.

Level: Hard8 of 10
Topics: Graph, Math, Matrix, Implementation
Solved: No attempts yet

Problem

A circuit has $N$ nodes and $M$ resistors. A resistor joins two different nodes, and two nodes can be joined by more than one resistor.

Push a current of 1 A into node 1 and draw the same current out of node $N$ . The potential difference between the two nodes is the total resistance between node 1 and node $N$ . Read the circuit and compute that total resistance.

Input

The first line has the number of nodes $N$ and the number of resistors $M$ . ( $2 < N \le 100$ , $1 \le M \le 300$ )

Each of the next $M$ lines describes one resistor as three integers $u$ , $v$ , $r$ , meaning a resistor of value $r$ joins node $u$ and node $v$ . ( $1 \le u, v \le N$ , $u \ne v$ , $1 \le r \le 100$ )

Not every node is guaranteed to be connected to node 1. The total resistance between node 1 and node $N$ is never infinite.

Output

Print the total resistance between node 1 and node $N$ , rounded at the third decimal place and written with exactly two decimals. When the exact value sits halfway between two candidates, round up. For an exact value of 79.595, print 79.60.

Examples2

Example 1

Input

Expected output

9.40

Example 2
Input
```
3 3
1 2 91
1 2 109
2 3 30
```
Expected output
```
79.60
```