eolymp
bolt
Try our new interface for solving problems
Problems

Drunken Walk

Drunken Walk

Time limit 1 second
Memory limit 64 MiB

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.

Input data

The input consists of multiple test cases. Each test case begins with a line containing two integers N, 2N10000, and M, 1M100000, the number of vertices and edges in the graph, respectively. The next M lines each contain three integers u, v, and w (1w1000), indicating that there is a directed edge from vertex u to vertex v (numbered from 0 to N−1) with weight w. The input terminates with a line with N = M = 0.

Output data

For each test case, print out a single line that contains the longest possible expected length of your walk. Your answer will be considered correct if it is within 10^{−6} absolute or relative precision.

Examples

Input example #1
4 5
0 1 2
0 2 1
0 3 3
1 3 1
2 3 4
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
0 0
Output example #1
2.00000000
3.66666667
Source 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011