Вам дан неорентированный взвешанный связанный граф из n вершин и m ребер. Назовем стоимостью пути значение максмимума среди весов ребер на пути. Пусть d(v,u) – это минимальная стоимость пути начинающегося в v и заканчивающегося в u. Посчитайте значение ∑1≤v<u≤nd(v,u) – сумма d(v,u) по всем парам (v,u).

В первой строке даны числа n(2≤n≤10^5) и m(n−1≤m≤3⋅10^5 – количество вершин и количество ребер.

В следующих m даны si, ti, wi(1≤si,ti≤n,1≤wi≤10^6) – описание ребра соеденяющего вершины si и ti с весом wi. Гарантируется что si≠ti.

Гарантируется что от каждой вершины можно добраться до любой другой двигаясь по рербам графа.

• Примеры
• входные данные
• 3 3
• 1 2 5
• 1 3 1
• 2 3 4
• выходные данные
• 9