제독 timer 1s memory 128MB

​미하일 안데르센 드 뤼터는 네덜란드의 역사에서 가장 유명한 제독으로 알려져 있으며 

17세기에 벌어진 영국-네덜란드 전쟁에서 전공을 세웠다.

뤼터가 살던 시절에 그래프 이론이 연구되기 시작했고, 제독은 이론을 해전 계획에 자주 이용했다.

바다 위의 중간 지점은 정점으로 나타낼 수 있고, 

각 중간 지점에서 이동할 수 있는 뱃길은 방향성이 있는 간선으로 나타나 있다. 

두 중간 지점 W1와 W2사이에 뱃길 W1 → W2는 최대 한 개 있을 수 있다. 

각 간선의 가중치는 그 뱃길을 안전하게 이동하기 위해 발사해야 하는 포탄의 수이다.

뤼터의 가장 유명한 전술은 이름 하여 뤼터작전이다. 

이 전술은 출발 지점에서 두 전함이 새로 다른 방향으로 출발을 한다. 

그 다음 적함과 전투를 하면서 이동하여 목적지에서 다시 만나는 전술이다. 

이 전술에서 두 전함은 항상 겹치지 않는 뱃길을 택해야 하며, 

출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지날 수 없다.

뤼터는 돈을 낭비하는 것을 좋아하지 않는다. 

그래서 가능한 한 포탄을 가장 적게 발사하는 뱃길을 택하려고 한다.

아래 입력 예에 대한 그림과 설명이다. 

두 함선(빨강, 파랑)은 1에서 시작해서 6에서 만난다.

빨간 함선은 1 → 3 → 6 (총 33개 포탄)으로 이동하고,

파란 함선은 1 → 2 → 5 → 4 → 6 (총 53개 포탄)으로 이동한다.

두 경로에서 출발과 도착을 제외하면 중복되는 정점과 간선이 없으므로 조건을 만족하면서 

두 함선이 발사한 포탄의 합은 86개로 가장 적은 개수이다.