Drunken Walk

After a few too many drinks in the evening, you set off on a long walk over a directed graph — but not endlessly long, because the graph has no cycles.

You start at vertex $0$. Whenever you are at a vertex, you leave it along one of its outgoing edges, choosing each outgoing edge at random with probability proportional to that edge's weight. You keep walking until you reach a vertex with no outgoing edges, at which point you fall asleep and the walk ends. The length of your walk is the number of edges you traverse.

Before you start (that is, before leaving vertex $0$), you may pick one edge anywhere in the graph that you dislike and ignore it for the entire walk, or you may choose to ignore no edge at all. Ignoring an edge removes it from the graph, so a vertex whose only outgoing edge you ignore becomes a place where you fall asleep.

Determine the largest possible expected length of your walk.

The input contains several test cases. Each test case starts with a line containing two integers $N$ and $M$ ($2 \le N \le 10{,}000$, $1 \le M \le 100{,}000$): the number of vertices and the number of edges of the graph. Each of the next $M$ lines contains three integers $u$, $v$, and $w$ ($1 \le w \le 1{,}000$), meaning there is a directed edge from vertex $u$ to vertex $v$ with weight $w$ (vertices are numbered from $0$ to $N-1$). The graph is guaranteed to contain no directed cycles. The input ends with a line containing $N = M = 0$, which must not be processed.

For each test case, print on its own line the largest possible expected length of your walk, rounded to exactly $8$ digits after the decimal point.