Problem in short: Consider an undirected graph of N nodes, M edges. Each edge is labeled with two integers A, B. Find a spanning tree of this graph which has the maximum possible value for the following expression:
\sum_{edges \in tree} \frac {A_{edge}}{B_{edge}}
Constraints: 1 <= N, M <= 10^5