Expected Path Length in a Directed Acyclic Graph

You are given a directed acyclic graph (DAG) with \(n\) nodes and \(m\) edges. The starting node is \(1\) and the destination node is \(n\). Each edge has an associated length. It is guaranteed that every node is reachable from the starting node and that the destination node can be reached from every node.

A frog starts at node \(1\) and moves toward node \(n\). When the frog is at a node with \(k\) outgoing edges, it chooses any of these edges with equal probability \(\frac{1}{k}\). When an edge from node \(u\) to node \(v\) with length \(w\) is taken, the frog adds \(w\) to its total path length.

Calculate the expected total path length from node \(1\) to node \(n\).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of nodes and edges, respectively).

Then \(m\) lines follow, each containing three integers \(u\), \(v\), and \(w\) (denoting a directed edge from node \(u\) to node \(v\) with length \(w\)).

outputFormat

Output a single number: the expected total length of the path from node \(1\) to node \(n\).

sample

3 3
1 2 3
1 3 2
2 3 4

4.5