Description

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?

Input Format

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 Format

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

4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

7.00

Hint

• 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