아침은 고구마야

준표는 살이 쪄버렸다. 체지방이 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$

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