소들은 체조(운동)를 싫어하지만 조깅은 조금 좋아합니다. 목장을 조사해 가능한 모든 길을 목록으로 만들었습니다. 길은 “방향성”이 있어 한 방향으로만 지날 수 있습니다. 두 점 사이 서로 반대 방향인 두 다른 길이 있을 수도 있습니다.

조깅할 가장 짧은 “순환 경로”를 구하세요. 같은 장소에서 시작하고 끝나는 경로입니다. 길이는 한 바퀴 돌며 지나는 길의 길이 합입니다.

길은 두 점을 연결합니다. 점은 양의 정수로, 1부터 연속으로 번호를 매깁니다. 거리도 양의 정수입니다.

주어진 모든 목장에 적어도 하나의 순환 경로가 있음이 보장됩니다.

입력

• $1$번째 줄: 방향성 길의 수 $N$ ($1 \le N \le 2000$); 서로 다른 점은 최대 400개입니다.
• $2..N+1$번째 줄: 길 하나의 시작점, 끝점, 거리(최대 1000).

출력

가능한 가장 짧은 순환 경로 거리를 정수 하나로 한 줄에 출력합니다.

예제

입력 1

4
3 1 5
1 2 4
2 3 3
1 3 44

출력 1

12

문제 출제: Hal Burch 및 Russ Cox