ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1266. Kirchhoff's Law

Time limit: 1.0 second
Memory limit: 64 MB
Vasya’s dad, as you know, is good in math but the son instead of following his father’s steps, studies physics at school. Once Vasya asked his father to help him to solve a simple problem — to find out the resistance of the resistors system. Dad answered him: “Here is nothing to think about. You are to numerate the conductors nodes, to write the I=U/R law for each conductor. Then remember that the sum of currents at each of the nodes except the first and the last equals to zero, you may assume potential in the first node equal to one and in the last node — zero. Then you get a simple system of linear equations. Hence you find potentials in the intermediate nodes and currents between all the nodes. It’s left only to divide the voltage by the total current from the first node and…
But Vasya is not good in math, so his dad was to write the system of equations himself and to solve it. Vasya looks at the end of the book of problems and says that there is another answer. Dad tried to solve the problem again and got another answer. Vasya looked at the answer and said again: “Wrong”. Dad resolves the problem for the third time and Vasya holds his own. Dad got tired to solve the problem manually and he decided to use a computer seeing that the students of mathematical department of the Ural State university are ready to write the required program.

Input

The first line contains integers N and M; N is a number of nodes in the circuit (2 ≤ N ≤ 20), M is the number of resistors (1 ≤ M < 1000). Each of the next M lines consists of three integers Ai, Bi и Ri — description of a resistor that has resistance Ri connecting the nodes Ai and Bi (1 ≤ Ai < BiN; 1 ≤ Ri ≤ 1000). There may be many resistors between two nodes.

Output

Your task is to output the total resistance between the nodes 1 and N rounded within two digits after a decimal points.

Sample

inputoutput
4 5
1 2 15
2 4 5
1 3 10
3 4 10
2 3 1
9.40
Problem Author: Alexander Klepinin (prepared Stanislav Vasilyev)
Problem Source: Ural State University championship, October 25, 2003