Minimum Construction Cost for Village Roads

You are given a village structured as an n × n grid of blocks. There are m proposed road segments connecting these blocks. Each road segment is described by four integers: u, v, w, and c, where u and v indicate the two blocks connected by the road, w is a weight (which is not significant for this task), and c is the construction cost.

Your task is to determine the minimum total construction cost needed so that every block in the village is reachable from any other block. In other words, you need to construct a spanning tree with the minimum sum of edge costs. Recall that a spanning tree on a graph with n nodes has exactly \(n-1\) edges.

Input Details: The input starts with two integers n and m. It is followed by m lines, each containing four integers representing a road segment.

Output Details: Output a single integer: the minimum total construction cost required to ensure connectivity among all blocks.

inputFormat

The input is provided via standard input (stdin) and has the following format:

n m
u1 v1 w1 c1
u2 v2 w2 c2
... 
um vm wm cm

Where:

• n: the number of blocks in one dimension (grid is n×n, but connectivity is considered over block identifiers 1 to n)
• m: the number of proposed road segments
• Each of the next m lines contains four integers: u, v, w, and c.

outputFormat

The output is a single integer printed to standard output (stdout) representing the minimum total construction cost required to connect all the blocks.

## sample

4 5
1 2 1 10
2 3 2 15
3 4 3 10
1 3 2 20
2 4 3 30

35