aprileasy-minimum-spanning-tree

You are given a weighted undirected graph consisting of N nodes (numbered from 0 to N) and M edges. Print the weight of it's Minimum Spanning Tree.

Note : The memory limits for this problem are extremely low. Have fun :)

Input :

The first line contains 6 integers N,  M,  X, A, C, and MOD.

Graph Generation :

Let the function getNext() be defined as follows.

getNext() {
    X = (X * A + C ) % MOD;
    return X;
}

Instead of getting the graph as input you will be generating the graph in your program. You will generate all the M edges one after the other. The i^th edge (between u[i] and v[i], of weight w[i]) is generated as follows

u[i] = getNext() % n;
v[i] = getNext() % n;
w[i] = getNext();

Output :

Print the weight of the Minimum Spanning Tree of the given graph.

Constraints :

1 ≤ N ≤ 100000

1 ≤ M ≤ 10000000

0 ≤ u, v < N 

All other input values fit in 32 - bit signed integers. 

Graph is guaranteed to be connected.

SAMPLE INPUT
5 7 37 47 57 67

SAMPLE OUTPUT
91

Explanation

The given input, leads to the following edges

(4 4 15) ,
(0 1 6) ,
(4 4 48) ,
(0 2 53) ,
(2 2 52) ,
(2 4 12) ,
(3 2 20)

The graph (with edges in the Minimum Spanning Tree highlighted in red) looks as follows:

Source: hackerearth | Difficulty: MEDIUM


Solutions: