Random Walk in a DAG#3378
You are exploring a directed graph with vertices and edges. The graph has no cycles. You start at vertex . At each vertex, you will randomly take one of its outgoing edges, with probability proportional to the weight of the edge.
You continue exploring until you reach a vertex that has no outgoing edges. The length of your exploration is the number of edges you traverse. Additionally, before starting your walk from vertex , you may choose to remove one edge from the graph (or you may choose not to remove any edge). Find the longest possible expected length of your walk, considering the best choice of an edge to ignore (or none).
The input consists of multiple test cases. Each test case begins with a line containing two integers , 2 \leq N \leq 10000, and , 1 \leq M \leq 100000 — the number of vertices and edges in the graph. The next lines each contain three integers , , and (1 \leq w \leq 1000), indicating that there is a directed edge from vertex to vertex (numbered from to N-1) with weight . The input terminates with a line containing N = M = 0.
For each test case, print a single line containing the maximum possible expected length of your walk. Your answer will be considered correct if it is within 10^{-6} absolute or relative precision.
Example 1