After having a bit too much to drink in the evening, you find yourself going on a long walk on a directed graph?but not too long, as there are no cycles. You start at vertex 0, and whenever you are at a vertex, you will randomly leave the vertex along one of its outgoing edges with probability proportional to the weight of the edge.

You continue walking until you reach a vertex that has no edges leaving it, after which you fall asleep. The length of your walk is the number of edges you traverse. Moreover, before leaving vertex 0, you may choose one edge from anywhere in the graph that you do not like and ignore it during your walk (or you may choose to not ignore any of them). Determine the longest possible expected length of your walk.

입력

• Each test case begins with a line containing two integers N, 2 ≤ N ≤ 10,000, and M, 1 ≤ M ≤ 100,000, the number of vertices and edges in the graph, respectively.
• The next M lines each contain three integers u, v, and w (1 ≤ w ≤ 1,000), indicating that there is a directed edge from vertex u to vertex v (numbered from 0 to N - 1) with weight w.

출력

Your answer will be considered correct if it is within 10^6 absolute or relative precision. In the first sample case, ignoring the edge from vertex 0 to vertex 3 gives the maximum possible expected length of 2. (Without ignoring it, the expected length is 1.5.)

입출력 예

입력

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

출력

2.00000000

입력

9 8
0 1 1
1 2 1
2 3 1
0 4 2
4 5 10
4 6 1
6 7 1
7 8 1

출력

3.66666667

출처:standford/2011/