We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Alex vs Fedor

Alex vs Fedor

In order to entertain themselves during the long flight, Alex and Fedor invented the following very simple two players game. The game is:

  • First, Alex draws some graph with bidirectional weighted edges. There are possibly multiple edges (probably, with different or same weights) in this graph.

  • Then Fedor picks some spanning tree of this graph. If the tree appears to be the minimal spanning tree, then the winner is Fedor. Otherwise, the winner is Alex.

We consider two trees different if the sets of the numbers of edges that are included in these trees are different. We consider two sets and different if there is at least one element that is present in and not present in or vice versa.

We should also mention that the graphs with enormous number of spanning trees upset Alex, as well as Fedor, so they will never have a graph that has more than spanning trees.

At some point, Fedor became too lazy to look for minimal spanning trees and now he just picks some arbitrary spanning tree from the Alex's graph. Each spanning tree has equal probability to be picked by Fedor. What is the probability of Fedor's victory now?

Input Format

The first line of input consists of two single space separated integers and - the number of nodes in Alex's graph and the number of edges in that graph, respectively.

Then there are lines, where the line has three numbers with the meaning that the edge with the number connects the nodes and and has the weight of .

Constraints

  • The graph is always connected.

Output Format

Output the probability of Fedor's victory, if he picks the spanning tree randomly, as an irreducible fraction.

Sample Input

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

Sample Output

1/4