P4316 Green Bean Frog's Home

With the launch of the new Baidu Space, the blog pet Green Bean Frog has completed its mission and is looking for its new home.

You are given a directed acyclic graph with $n$ vertices and $m$ edges. The start vertex is $1$, and the terminal vertex is $n$. Each edge has a length. From the start, every vertex is reachable, and every vertex can reach the terminal. Green Bean Frog starts from the start and moves to the terminal. Upon arriving at a vertex that has $k$ outgoing edges, the frog may choose any outgoing edge to leave the vertex, and each edge is chosen with probability $\frac{1}{k}$. What is the expected total length of the path from the start to the terminal?

The first line contains two integers representing the number of vertices $n$ and the number of edges $m$. Lines $2$ through $(m + 1)$ each contain three integers $u, v, w$, indicating there is a directed edge from $u$ to $v$ with length $w$.

Output a single real number: the answer, rounded to two decimal places.

- Constraints - For $20\%$ of the testdata, $n \leq 10^2$. - For $40\%$ of the testdata, $n \leq 10^3$. - For $60\%$ of the testdata, $n \leq 10^4$. - For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 2 \times n$, $1 \leq u, v \leq n$, $0 \leq w \leq 10^9$, and the graph has no parallel edges or self-loops. Translated by ChatGPT 5