제독

미힐 더 라위터르는 네덜란드 역사에서 가장 유명한 제독이다. 그는 17세기에 벌어진 영국-네덜란드 전쟁에서 큰 전공을 세웠다.

라위터르가 살던 시절에 막 그래프 이론이 연구되기 시작했고, 제독은 이 이론을 해전 계획에 자주 활용했다. 바다 위의 중간 지점은 정점으로, 각 중간 지점에서 다른 지점으로 이동할 수 있는 뱃길은 방향이 있는 간선으로 나타낸다. 두 중간 지점 $u$와 $w$ 사이의 뱃길 $u \to w$는 최대 한 개만 존재한다. 각 간선의 가중치는 그 뱃길을 안전하게 지나기 위해 발사해야 하는 포탄의 수이다.

라위터르의 가장 유명한 전술은 "De Ruyter Manoeuvre"이다. 이 전술에서는 하나의 중간 지점에서 두 전함이 서로 다른 방향으로 출발한다. 각 전함은 적함과 전투하며 이동한 뒤, 목적지에서 다시 만난다. 이때 두 전함은 겹치지 않는 뱃길을 택해야 하며, 출발 지점과 목적지를 제외하고는 같은 중간 지점이나 같은 뱃길을 지나서는 안 된다.

라위터르는 돈을 낭비하기를 싫어한다. 따라서 발사하는 포탄의 총합이 가장 적어지도록 두 전함의 뱃길을 정하려고 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 입력의 끝은 파일의 끝(EOF)으로 판별한다.

각 테스트 케이스의 첫째 줄에 중간 지점의 수 $v$와 뱃길의 수 $e$가 주어진다 ($3 \le v \le 1000$, $3 \le e \le 10000$). 이어지는 $e$개의 줄에는 각 뱃길의 정보 $a_i$, $b_i$, $c_i$가 주어진다 ($1 \le a_i, b_i \le v$, $a_i \ne b_i$, $1 \le c_i \le 100$). $a_i$는 뱃길의 시작 지점, $b_i$는 도착 지점이며, $c_i$는 그 뱃길을 지날 때 발사해야 하는 포탄의 수이다.

전술의 시작 지점은 $1$번, 목적지는 $v$번 지점이다. $1$번과 $v$번 지점 사이에는 서로 겹치지 않는 경로가 항상 두 개 이상 존재한다.

각 테스트 케이스마다, 두 전함이 이 전술을 따를 때 발사해야 하는 포탄의 최소 총합을 한 줄에 하나씩 출력한다.

첫 번째 테스트 케이스에서 두 전함(빨강, 파랑)은 $1$번에서 출발하여 $6$번에서 만난다. 빨간 전함은 $1 \to 3 \to 6$(포탄 $33$개), 파란 전함은 $1 \to 2 \to 5 \to 4 \to 6$(포탄 $53$개)으로 이동한다. 출발 지점과 도착 지점을 제외하면 두 경로에는 겹치는 정점이나 간선이 없으며, 포탄의 총합은 $86$개이다.