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.
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 < Bi ≤ N; 1 ≤ Ri ≤ 1000). There may be many resistors between two nodes.
Your task is to output the total resistance between the nodes 1 and N rounded within two digits after a decimal points.
1 2 15
2 4 5
1 3 10
3 4 10
2 3 1
Problem Author: Alexander Klepinin (prepared Stanislav Vasilyev)
Problem Source: Ural State University championship, October 25, 2003