MST and Rectangles

You have a 2D array A of size $N \times N$. Each cell initially contains 0.

You are also given Q queries of the form X1 X2 Y1 Y2 W, which means you should perform the following operation on A:

• For each pair of integers (i, j) where X1 ≤ X2 < Y1 ≤ Y2 and X1 ≤ i ≤ X2 and Y1 ≤ j ≤ Y2 , add W to the value of cell A[i][j] and A[j][i].

Consider an undirected graph G with N vertices. For each 1 ≤ i, j ≤ N, there is an edge connecting vertices i and j with cost A[i][j]. Calculate the cost of Minimum Spanning Tree of G.

The first line contains a single integer N, Q.

The next Q lines contain five integers X1 X2 Y1 Y2 W, describing a query.

Print the cost of Minimum Spanning Tree of G.

•  $1 \le N, Q \le 10^5$ 
•  $1 \le X\_1 \le X\_2 < Y\_1 \le Y\_2 \le N$ 
•  $|W| \le 10^6$