The Real Value of Mats
By Marcio T. I. Oshiro 
Brazil
By Marcio T. I. Oshiro Brazil
Arab mats are well known. Its quality is recognized around the world, and the characteristics of a good carpet are appreciated by all. Rate mats is a very difficult task, and experts analyze its features thoroughly to establish an appropriate price. The mats are formed by points where the wires are strung. Despite being very difficult for the average person, experts are able to tell the direction in which the wire was strung between two points. These wires form circuits in complicated patterns and they have hundreds or even thousands of circuits and are very intricate. Large circuits (where the amount of wire divided by the number of nodes is very large) devalue the carpet, because make it less resistant. Small circuits are valued, and the appraiser always seeks to find the lowest existing rug in circuit, as this is an indicator of the value of the rug. Your task in this exercise is to read data from a carpet with N nodes and M threads (connections between these nodes in the direction that was taken is determined) and determine the value of the minor circuit in the carpet, or the circuit in which the ratio between the quantity of yarn divided by the number of nodes is minimal.
The entry consists of several instances and ends with the end of file (EOF).
The first line of each instance contains two integers, N (3 ≤ N ≤ 1.000) and M (N ≤ M ≤ N × N - 1), corresponding to the number of nodes and links, respectively. The nodes are numbered from 1 to N. The following M lines, each with three integers u, v and c (0 ≤ c ≤ 1.000) describing a link from node u to node v using c cm wire.
For each instance, print in a single line the minimum value of a circuit in the carpet, where this value is the ratio between the amount of wire divided by the number of nodes in the circuit. The value must be printed with 3 decimal places. Print -1 if there is no circuit in the carpet.
| Sample Input | Sample Output |
|
3 3 |
-1 |