class UnionFind: def __init__(self, n): self.n = n self.parent_or_size = [-1] * n def merge(self, a, b): x = self.root(a) y = self.root(b) if x == y: return False if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x self.parent_or_size[x] += self.parent_or_size[y] self.parent_or_size[y] = x return True def same(self, a, b): return self.root(a) == self.root(b) def root(self, a): if self.parent_or_size[a] < 0: return a self.parent_or_size[a] = self.root(self.parent_or_size[a]) return self.parent_or_size[a] def size(self, a): return -self.parent_or_size[self.root(a)] N, M = map(int, input().split()) uf = UnionFind(N) def valtotuple(val: int): a = val % N val //= N b = val % N c = val // N return c, a, b def tupletoval(tup) -> int: c, a, b = tup return c * N * N + a * N + b es = [] for i in range(M): a, b, c = map(int, input().split()) es.append(tupletoval((c, a - 1, b - 1))) es.sort() ans = 0 for val in es: c, a, b = valtotuple(val) if not uf.same(a, b): ans += c * uf.size(a) * uf.size(b) uf.merge(a, b) print(ans)