UltraNet 최적화

UltraNet 회사는 한 나라의 모든 도시에 네트워크 연결을 제공한다. 두 도시는 직접 연결되거나 간접 연결된다. 도시 i와 도시 j가 직접 연결된다는 것은 두 도시 사이에 대역폭이 bi,j = bj,i로 대칭인 케이블이 연결되어 있다는 뜻이다. 직접 연결되지 않은 두 도시 사이에도 적어도 하나의 경로가 존재한다. 현재 UltraNet에서는 같은 도시 쌍에 여러 경로가 있을 수 있다.

현재 UltraNet은 완벽하게 동작하지만 각 케이블의 유지비가 비싸다. 에너지 절약도 중요한 문제다. 케이블의 에너지 소비량은 대역폭에 비례한다. 따라서 회사는 다음 순서의 정책에 따라 네트워크를 재구성하는 최적화 계획을 세웠다.

1. 전체 UltraNet의 연결성을 해치지 않으면서 케이블 수를 최소화해야 한다. 즉, 모든 도시 쌍 사이에 정확히 하나의 경로만 있어야 한다.
2. 케이블 수를 최소화하는 방법이 여러 가지라면, 전체 네트워크의 병목을 최대화해야 한다. 네트워크의 병목은 대역폭이 가장 좁은 도시 쌍으로 결정되며, 도시 쌍 (i, j)의 대역폭 b'i,j는 i에서 j로 가는 유일한 경로 위에서 대역폭이 가장 좁은 케이블로 결정된다.
3. 위 두 조건을 만족하는 방법이 여전히 여러 가지라면, 네트워크의 총 에너지 소비량을 최소화해야 한다. 즉, 남은 케이블들의 대역폭 합을 최소화해야 한다.

여러분은 UltraNet의 네트워크 최적화를 도와, 최적화된 네트워크에서 모든 도시 쌍 사이의 대역폭 합을 출력해야 한다. 다음 예시를 최적화하면 점선으로 표시된 세 개의 케이블이 버려진다. 그 결과 네트워크에서 병목은 3이고, 남은 네 개 케이블의 대역폭 합은 6 + 3 + 8 + 4 = 21이며, 모든 도시 쌍 사이의 대역폭 합은 \(\sum_{i=1}{^n-1}\sum_{j=i+1}^{n}\)b'i,j = 6 + 4 + 6 + 3 + 4 + 8 + 3 + 4 + 3 + 3 = 44이다.

각 테스트 케이스는 도시의 수 n과 케이블의 수 m을 나타내는 두 정수로 시작한다. 그다음 m개의 케이블을 명시하는 m개의 줄이 주어진다. m개의 줄 각각은 세 개의 양의 정수 i, j, bi,j를 포함하며, 이는 대역폭 bi,j인 케이블이 도시 쌍 (i, j)를 직접 연결한다는 뜻이다. 도시는 1부터 n까지 번호가 매겨지고 bi,j = bj,i이므로 i < j이다. 현재 네트워크에서 모든 도시 쌍 사이에는 케이블이 하나 이하로 존재한다. 또한 모든 케이블의 대역폭은 서로 다르다. 같은 대역폭 값을 가진 케이블은 없다.

최적화된 네트워크에서 모든 도시 쌍의 대역폭 합을 나타내는 정수 하나를 출력한다.

• 2 ≤ n ≤ 10000
• 1 ≤ m ≤ 500000
• 1 ≤ i < j ≤ n
• 0 < bi,j < 107