제독

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

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

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

라위터르는 돈을 낭비하는 것을 좋아하지 않는다. 따라서, 포탄을 가장 적게 발사하는 뱃길을 택하려고 한다.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 입력의 끝은 EOF로 확인할 수 있다.

테스트 케이스의 첫째 줄에는 중간 지점의 수 v와 뱃길의 수 e가 주어진다. (3 ≤ v ≤ 1000, 3 ≤ e ≤ 10000) 다음 e개 줄에는 뱃길의 정보 ai, bi, ci가 주어진다. (1 ≤ ai, bi ≤ v, ai ≠ bi, 1 ≤ ci ≤ 100) ai는 뱃길의 시작 지점, bi는 도착 지점, ci는 그 뱃길로 이동할 때 발사해야 하는 포탄의 수이다.

전술의 시작 지점은 1이고, 목적지는 v이다. 항상 1과 v사이에 겹치지 않는 경로가 적어도 두 개 있다.

각 테스트 케이스에 대해서, 두 전함이 전술을 따르면서 발사해야 하는 포탄의 최소 개수를 출력한다.

두 함선(빨강, 파랑)은 1에서 시작해서 6에서 만난다. 빨간 함선은 1 → 3 → 6 (총 33개 포탄)으로 이동하고, 파란 함선은 1 → 2 → 5 → 4 → 6 (총 53개 포탄)으로 이동한다. 두 경로에서 출발과 도착을 제외하면 중복되는 정점과 간선이 없다.