20425번 - 아침은 고구마야 (Easy)

입력 제한 외 난이도에 따른 문제의 차이는 없다.

준표는 살이 쪄버렸다. 무려 체지방 25%의 비만이다. 준표는 균형 잡힌 식습관을 위해 아침마다 고구마를 먹기 시작했다. 아침마다 고구마를 먹던 준표는 고구마의 진정한 맛에 눈을 뜨고, 직접 고구마밭을 꾸려 매일 아침 최고의 고구마를 캐 먹기로 했다.

<그림 1> 고구마 그래프 예시

고구마는 크게 지상부와 지하부로 나뉘어 있으며, 준표는 지하부에만 관심이 있다. 준표는 고구마의 지하부를 추상화한 그래프를 고구마 그래프 라고 부르기로 했다.

고구마 그래프는 크게 다섯 종류의 그래프로 나눌 수 있는 연결된 방향성 없는 그래프 이며, 각 간선마다 간선의 강도 c를 가지고 있다.

1. 고구마 그래프의 루트

   고구마 그래프를 구성하는 정점 중 지상부와 연결된 단 하나의 정점이다. 이 정점은 언제나 1번 정점이다.

2. 굳은 뿌리

   굳은 뿌리는 고구마 그래프의 루트, 즉 1번 정점을 루트로 하는 트리 구조로 되어있다. 즉 임의의 두 정점은 모두 연결되어 있으며 경로가 하나뿐이다.

3. 덩이뿌리(고구마)

   우리가 흔히 말하는 고구마의 먹는 부분이다. 하나의 덩이뿌리는 굳은 뿌리의 끝 중 하나에 연결되어있으며, 덩이뿌리를 구성하는 정점이 N개라면 볼록 N각형과 같은 모양으로 그려진다. 즉 단순 사이클이다.

   덩이뿌리의 질량은 덩이뿌리를 구성하는 정점 개수의 제곱으로 계산된다. 예를 들어, 덩이뿌리가 5개의 정점으로 구성되어있다면 덩이뿌리의 질량은 5²=25이다.

4. 가는 뿌리

   가는 뿌리는 덩이뿌리의 굳은 뿌리와 연결된 정점을 제외한 모든 정점에 달려있으며, 트리 구조로 되어있다.

5. 뿌리의 끝

   덩이뿌리가 달려있지 않은 굳은 뿌리의 끝과 가는 뿌리의 끝, 즉 고구마 그래프의 단말 정점이다. 뿌리의 끝은 땅과 강하게 얽혀있어 뿌리를 뽑게 되면 땅속에 남을 수밖에 없다.

준표는 고구마를 얻기 위해 "고구마 그래프의 루트"를 잡고 일 순간 아주 강한 힘으로 잡아당겨 땅에서 뽑아낸다. 고구마 그래프를 뽑아내면 고구마 그래프는 "밖으로 뽑혀 나오는 정점" 과 "땅속에 남는 정점"으로 양분된다. 고구마 그래프의 모든 정점은 두 부분 중 하나에 속해야만 하며, 모든 "밖으로 뽑혀 나오는 정점"은 고구마 그래프의 루트와 연결되어있으며, 모든 "땅속에 남는 정점"은 임의의 뿌리의 끝과 연결되어있다.

그래프가 양분되기 위해선 고구마 그래프의 간선 중 일부가 끊겨야 할 것이다. 고구마 그래프는 항상 "끊기는 간선 강도의 총합"이 최소가 되도록 끊긴다. 운이 나쁘면, 덩이뿌리(고구마)를 구성하는 간선이 끊어지는 경우가 있을 수 있다. 이러한 경우를 고구마가 깨졌다고 표현한다. 당연하지만 준표는 고구마 마스터이기 때문에 뽑히는 덩이뿌리의 질량이 최대가 되도록 고구마 그래프를 뽑을 수 있고, 준표는 최고의 고구마만을 취급하므로 깨진 고구마는 셈에 포함하지 않는다.

준표가 고구마 그래프를 뽑아 수확하는 고구마의 총 질량을 알려주자.

첫 줄에 고구마 그래프를 구성하는 정점의 개수 N, 간선의 개수 M를 입력받는다.

이후 M 줄에 걸쳐 간선의 정보가 주어진다. 간선의 정보는 세 정수 u, v, c로 주어진다. 이는 정점 u와 정점 v를 연결하는 강도 c의 간선을 의미한다.

준표가 수확하게 되는 고구마의 총 질량을 출력한다.

2 ≤ N ≤ 1,000,000

N - 1 ≤ M ≤ 2,000,000

1 ≤ u, v ≤ N, u ≠ v

1 ≤ c ≤ 1,000,000,000

굳은 뿌리, 덩이뿌리의 간선이 끊어져 땅속에 고구마(덩이뿌리의 정점)를 남기는 경우는 없다.