산봉우리와 계곡

잘 알려진 지형을 따라 긴 하이킹 여행을 계획하고 있습니다. 가보고 싶은 장소는 $N$곳이고, 이들을 잇는 산책로는 $M$개입니다. 각 산책로에는 양의 정수 난이도가 주어집니다.

이 산책로 체계에는 특별한 점이 있습니다. 난이도가 1인 산책로는 정확히 $N-1$개이며, 이들은 완전히 평평한 길입니다. 나머지 산책로의 난이도는 모두 $\lceil N/3 \rceil$ 이상이며, 매우 험한 산길입니다. ($\lceil x \rceil$는 $x$ 이상인 가장 작은 정수입니다.)

난이도 1인 산책로만으로 임의의 두 장소 사이를 오갈 수 있습니다.

모든 장소를 최소 한 번씩 방문해야 합니다. 출발점은 어느 장소든 고를 수 있고, 도착점은 출발점과 다른 장소여야 합니다. 난이도의 합이 최소가 되는 경로를 구하세요. 난이도 $d$인 산책로를 총 $k$번 걸으면 합에 $k \cdot d$가 더해집니다.

첫째 줄에 공백으로 구분된 정수 $N$($4 \le N \le 500000$)과 $M$($N-1 \le M \le 2000000$)이 주어집니다. 다음 $M$개의 줄에는 각각 공백으로 구분된 정수 $x_i$, $y_i$, $w_i$가 주어지며, 이는 장소 $x_i$와 $y_i$를 난이도 $w_i$인 산책로가 잇는다는 뜻입니다($1 \le i \le M$, $0 \le x_i, y_i \le N-1$, $x_i \ne y_i$). 두 장소를 잇는 산책로는 최대 하나입니다. 각 $w_i$는 1이거나 $\lceil N/3 \rceil \le w_i \le N$을 만족합니다.

모든 장소를 적어도 한 번 방문하는 경로 중 난이도 합의 최솟값을 정수 하나로 출력합니다.

첫 번째 그림은 난이도 1인 산책로만 나타냅니다.

두 번째 그림은 모든 산책로를 난이도와 함께 나타냅니다.

세 번째 그림은 난이도 1인 산책로를 뺀 나머지 산책로를 나타냅니다.

최적 경로는 4 → 1 → 0 → 2 → 5 → 2 → 6 → 7 → 3 → 8이며, 총 비용은 1 + 1 + 1 + 1 + 1 + 1 + 3 + 1 + 1 = 11입니다. 이보다 낮은 난이도 합으로 모든 장소를 방문하는 경로는 없습니다.