Вам дан неорентированный взвешанный связанный граф из 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