Following Flow

The world has $N+1$ vertices, numbered $0$ through $N$. Edges run between the vertices. Every edge is one way, and each edge takes its own amount of time to cross. Donghyun is standing at vertex $0$, and vertex $N$ is his home.

Until he reaches home, Donghyun wanders wherever the mood takes him. Wandering means that he picks one of the edges leaving his current vertex, each with the same probability, and follows it to the next vertex. When several edges join the same pair of vertices, each one counts as a separate edge. An edge that returns to its own vertex is also possible. Once he arrives at vertex $N$, he stops there.

Compute the expected time it takes him to get from vertex $0$ to his home.

For example, suppose the world looks like the picture below.

At vertex $0$ Donghyun spends time $1$ to move to vertex $1$ with probability $1/2$, or spends time $1$ to move to vertex $2$ and reach home. At vertex $1$ he spends time $2$ to return to vertex $0$ with probability $1/2$, or spends time $2$ to reach home. The answer in this case is

$\frac{1}{2}\times 1+\left(\frac{1}{2}\right)^{2}\times(1+2)+\left(\frac{1}{2}\right)^{3}\times(1+2+1)+\cdots=\frac{8}{3}$

The first line has $N$ $(1 \le N \le 30)$, the number of vertices, and $M$ $(1 \le M \le 1\,000)$, the number of edges, separated by a space. Note that the real number of vertices is $N+1$.

Each of the next $M$ lines has $x$, $y$, $t$ $(0 \le x < N,\ 0 \le y \le N,\ 1 \le t \le 50)$ separated by spaces, meaning that an edge runs from vertex $x$ to vertex $y$ and takes time $t$ to cross. The edges are given so that every vertex has a path to vertex $N$. Every vertex from $0$ to $N-1$ therefore has at least one outgoing edge.

Print on one line the expected time to get from vertex $0$ to home, vertex $N$, rounded to exactly six digits after the decimal point. Print all six digits even when the value is an integer. The answer never exceeds $10^{6}$, and no input makes the rounding at the sixth decimal digit ambiguous.