미니언들의 놀이
시간 제한2초메모리 제한256 MB
가중치가 있는 무방향 그래프에서 단순 사이클을 골라 그 위 간선 가중치의 최솟값과 최댓값의 합이 최대가 되도록 하는 값을 구한다.
문제
그루가 가게에 간 사이, 미니언들은 너무 심심해서 할 일이 없었다. 미니언들은 스스로를 달래기 위해 대회를 하나 열었고, 모든 미니언이 참가하기로 했다.
대회의 내용은 다음과 같다. 그루의 연구소 지도에는 n개의 검문 지점이 표시되어 있다. 검문 지점 사이에는 m개의 양방향 통로가 있고, 각 통로에는 바나나가 몇 개씩 놓여 있다. 미니언은 아무 검문 지점에서나 출발해 통로를 따라 달리다가 다시 출발 지점으로 돌아온다. 이때 미니언은 어떤 통로도 두 번 이상 지나지 않는다.
미니언이 이런 닫힌 경로를 따라 달리면서 바나나가 c1, c2, ..., ck개 놓인 통로를 차례로 지났다면, 그 경로로 얻는 점수는 min(c1, c2, ..., ck) + max(c1, c2, ..., ck)이다.
데이브도 이 대회에 참가했고, 우승을 매우 원한다. 그래서 데이브는 여러분에게 도움을 청했다. 데이브가 최대한 많은 점수를 받을 수 있는, 즉 점수가 최대가 되는 닫힌 경로를 찾도록 도와주자. 이 귀여운 생명체의 부탁을 거절하지 말고 도와주자!
입력
첫째 줄에 두 정수 n과 m이 주어진다 (1 ≤ n, m ≤ 105). n은 검문 지점의 수, m은 검문 지점 사이의 통로 수이다.
다음 m개 줄에는 검문 지점 사이의 통로에 대한 설명이 주어진다. i번째 줄에는 세 정수 v, u, w가 주어진다 (1 ≤ v, u ≤ n; v ≠ u; 0 ≤ w ≤ 109). v와 u는 i번째 통로가 잇는 두 검문 지점의 번호이고, w는 그 통로에 놓인 바나나의 수이다.
출력
모든 닫힌 경로 중에서 바나나 수의 최솟값과 최댓값의 합이 가질 수 있는 최댓값을 출력한다. 지도에 닫힌 경로가 하나도 없으면 0을 출력한다.