그래프와 사이클

정점이 n개인 무방향 가중 완전 그래프가 주어지며, n은 홀수이다.

크기 k의 사이클 배열(cycle-array)은 다음 성질을 만족하는 간선의 배열 [e1, e2, . . . , ek]로 정의한다.

• k는 1보다 크다.
• 1부터 k까지의 임의의 i에 대해, 간선 ei는 간선 ei−1과 정확히 하나의 공통 정점을 가지며, 간선 ei+1과도 정확히 하나의 공통 정점을 가진다. 그리고 이 정점들은 서로 다르다. (e0 = ek, ek+1 = e1으로 간주한다.)

사이클 배열에 속한 간선들은 분명히 사이클을 이룬다.

f(e1, e2)는 간선 e1과 e2를 매개변수로 받아 두 간선의 가중치 중 최댓값을 반환하는 함수로 정의한다.

사이클 배열 C = [e1, e2, . . . , ek]에 대해, 사이클 배열의 가격은 1부터 k까지의 모든 i에 대한 f(ei, ei+1)의 합으로 정의한다. (ek+1 = e1으로 간주한다.)

그래프의 사이클 분할(cycle-split)은 서로 겹치지 않는 사이클 배열들의 집합으로, 이들의 합집합이 그래프의 모든 간선을 포함하는 것으로 정의한다. 사이클 분할의 가격은 그에 속한 배열들의 가격의 합으로 정의한다.

그래프에는 여러 가지 사이클 분할이 존재할 수 있다. 그래프가 주어졌을 때, 가격이 최소인 사이클 분할을 찾고 그 가격을 출력하시오.

첫째 줄에는 정점의 개수 n이 주어진다. (3 ≤ n ≤ 999, n은 홀수)

다음 n·(n−1)/2개의 각 줄에는 공백으로 구분된 세 정수 u, v, w가 주어진다. (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10^9) 이는 정점 u와 v 사이에 가중치 w의 간선이 있음을 나타낸다.

그래프의 사이클 분할 중 가능한 최소 가격을 나타내는 정수 하나를 출력한다.

각 간선을 입력에 나타난 순서대로 번호를 매기자. ei는 입력에서 i번째로 나타난 간선을 의미한다.

첫 번째 예시에서 가능한 유일한 사이클 분할은 S = {[e1, e2, e3]}이다. f(e1, e2)+f(e2, e3)+f(e3, e1) = 1+1+1 = 3이다.

두 번째 예시에서 최적인 사이클 분할은 S = {[e3, e8, e9], [e2, e4, e7, e10, e5, e1, e6]}이다. [e3, e8, e9]의 가격은 12이고, [e2, e4, e7, e10, e5, e1, e6]의 가격은 23이므로 분할의 가격은 35이다.