저가 항공 노선

유스타스(Justas)는 여객기를 만들었고, 이제 저가 항공사인 유스타스 항공(Justas Airlines)을 세우려고 합니다.

유스타스는 관광객에게 인기 있는 도시 $N$개의 목록을 만들고, 이 도시들을 잇는 노선 중 어떤 노선이 수익을 낼 수 있는지 계산했습니다. 각 노선은 두 도시를 연결하며, 노선의 수익성은 유스타스 항공이 그 노선을 한 달 동안 운항할 때 얻는 월 수익(유로)을 나타냅니다.

운항할 노선들은 어떤 두 노선을 골라도 공통으로 지나는 도시가 하나 있도록 선택해야 합니다. 유스타스 항공이 한 달에 낼 수 있는 최대 수익을 구하세요.

첫째 줄에 도시의 수 $N$과 수익을 낼 수 있는 노선의 수 $M$이 주어집니다. 도시에는 $1$부터 $N$까지 번호가 매겨져 있습니다.

다음 $M$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $p_i$가 주어집니다. $a_i$와 $b_i$는 $i$번째 노선이 연결하는 두 도시이고, $p_i$는 그 노선의 수익성입니다. 같은 두 도시를 연결하는 노선은 두 개 이상 존재하지 않습니다.

가능한 최대 수익을 정수 하나로 출력합니다.

• $1 \le N \le 300000$
• $1 \le M \le 500000$
• $1 \le a_i, b_i \le N$
• $1 \le p_i \le 1000000000$