Minimum Spanning Tree on Complete Graph with Special Edge Weights

You are given an undirected complete graph with \( n \) vertices and \( m \) triples \(P_1, P_2, \dots, P_m\) where \(P_i = (u_i, v_i, w_i)\). It is guaranteed that \(1 \leq u_i < v_i \leq n\), and for any two triples \(P_i\) and \(P_j\) with \(i \neq j\) we have \((u_i,v_i) \neq (u_j,v_j)\).

For any two vertices \(x\) and \(y\) in the graph with \(1 \le x < y \le n\), the weight of the edge connecting them is defined as follows:

• If there exists a triple \(P_i\) satisfying \(u_i=x\) and \(v_i=y\), then the weight of the edge is \(w_i\).
• Otherwise, the weight of the edge is \( |x-y| \).

Your task is to compute the total weight of the edges in the minimum spanning tree (MST) of this graph.

Note: If there exists a special weight provided for an edge, you must use that weight rather than \(|x-y|\>.

inputFormat

The first line contains two integers \( n \) and \( m \) \((1 \le n, m \le \text{constraints})\), representing the number of vertices and the number of special triples, respectively.

The next \( m \) lines each contain three integers \( u, v, w \) representing a triple \( P_i = (u, v, w) \) with \(1 \le u < v \le n\). It is guaranteed that each undirected edge appears at most once among the \( m \) triples.

outputFormat

Output a single integer, the total weight of the edges in the minimum spanning tree of the graph.

sample

4 2
1 3 1
2 4 1

3