아침은 고구마야

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

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

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

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

1. 고구마 그래프의 루트

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

2. 굳은 뿌리

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

3. 덩이뿌리(고구마)

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

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

4. 가는 뿌리

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

5. 뿌리의 끝

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

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

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

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

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

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

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

$2 \le N \le 1{,}000{,}000$

$N - 1 \le M \le 2{,}000{,}000$

$1 \le u, v \le N$, $u \ne v$

$1 \le c \le 1{,}000{,}000{,}000$

덩이뿌리의 간선이 끊어지는 일은 없다.