I got this question in one of my interviews. Let me state the problem statement clearly,

"You're given an undirected weighted graph consisting of N nodes and E edges and all the weights are unique ( meaning no weights will have duplicates ). Note the graph may also be disconnected ( there could be more than one component in your graph ). The nodes in the graph are labelled starting from 1 to N."

Now you're given an operation that you could perform which is, cut( u , v ) , where u is the label of one node and v is the label of another node and u < v . what this operation returns as result for the given u and v is that it takes the minimum weighted edge adds its value to result and then removes it from graph and then checks whether u and v are disconnected if they are disconnected it stops and returns the result. If the u and v are still connected by some means then it checks for the next minimum weighted edge in the graph and adds its value to the existing result value and removes the edge from the graph and then again check whether u and v are disconnected, if disconnected it stops and returns result. If not then again it continues the same procedure with the next minimum weighted edge in the graph.

So now the question is calculate the sum of all cut(u,v) for all u and v pairs in the graph where u < v . Like if N = 3 and say E = 5, (1,2), (1,3), (2,3) will be the all possible (u,v) pairs where u < v, where u and v are labels of the node. Then final SUM = cut(1,2)+cut(1,3)+cut(2,3). As the answer might be big MOD the value with 1e9+7.

So this is the question I got in my interview and I didn't have enough time to process this question and it seemed pretty hard too. And when I asked for hint, use disjoint set data structures was the reply. I had no clue on how to proceed it further. Can some body provide ideas and different approaches that could be taken to solve this problem.Thanks.