Bruce has a directed weighted graph ~G = (V, E)~, and the weight of each edge ~(x, y)~ is denoted as ~w_{xy}~ (~w_{xy}~ can be negative). For any cycle in the graph, Bruce defined the cycle's weight as the average edges' weight in the cycle. For example, the weight of cycle ~(c_1, c_2, \dots, c_k, c_1)~ is calculated by ~\left(w_{c_1, c_2}+w_{c_2, c_3}+\dots+w_{c_{k-1}, c_k}+w_{c_k, c_1}\right)/k~, where ~k~ is the number of edges in this cycle. Now, Bruce's objective is to find the cycle which has the minimal weight in ~G~.

Input Specification

The first line of input will consist of two integers, ~N~ and ~M~, which are the number of vertices and the number of edges.

Each of the next ~M~ lines will consist of three numbers, ~x~, ~y~ and ~z~ (~1 \le x, y \le N~, ~-10^7 \le z \le 10^7~), which are the edge from ~x~ to ~y~ with the cost ~z~.

Output Specification

Output the minimal cycle's weight. Answers will be considered correct if they are within an absolute or relative error less than or equal to ~10^{-8}~.

Constraints

For all subtasks:

~N \le 3\,000~

~M \le 10\,000~

Subtask 1 [20%]

~N \le 100~

~M \le 1\,000~

Subtask 2 [50%]

~N \le 1\,000~

~M \le 5\,000~

Note that all test cases are randomly generated.

Sample Input 1

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

Sample Output 1

3.66666667

Sample Input 2

2 2
1 2 -2.9
2 1 -3.1

Sample Output 2

-3.00000000