아침은 고구마야

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

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