포털

Bessie는 $N$ ($2\le N\le 10^5$)개의 정점 $1\ldots N$과 $2N$개의 포털 $1\ldots 2N$으로 이루어진 네트워크에 있다. 각 포털은 서로 다른 두 정점 $u$와 $v$ ($u\neq v$)를 연결한다. 같은 두 정점을 여러 포털이 연결할 수도 있다.

각 정점 $v$는 서로 다른 네 개의 포털과 인접하다. $v$에 인접한 포털의 목록은 $p\_v=\[p\_{v,1},p\_{v,2},p\_{v,3},p\_{v,4}]$로 주어진다.

현재 위치는 순서쌍 $(\text{현재 정점}, \text{현재 포털})$, 즉 $(v,p\_{v,i})$ ($1\le v \le N$, $1\le i\le 4$)로 나타낼 수 있다. 다음 두 연산 중 하나로 현재 위치를 바꿀 수 있다.

1. 현재 포털을 통해 이동하여 현재 정점을 바꾼다.
2. 현재 포털을 전환한다. 각 정점에서 목록의 처음 두 포털은 서로 짝지어지고, 마지막 두 포털도 서로 짝지어진다. 즉 현재 위치가 $(v,p\_{v,2})$라면 포털 $(v,p\_{v,1})$로 전환할 수 있고, 그 반대도 가능하다. 마찬가지로 현재 위치가 $(v,p\_{v,3})$이라면 포털 $(v,p\_{v,4})$로 전환할 수 있고, 그 반대도 가능하다. 다른 전환은 허용되지 않는다. 예를 들어 포털 $p\_{v,2}$에서 포털 $p\_{v,4}$로 전환할 수 없다.

총 $4N$개의 서로 다른 위치가 있다. 안타깝게도 모든 위치에서 다른 모든 위치로 연산을 통해 도달할 수 있다는 보장은 없다. 따라서 $c\_v$ ($1\le c\_v\le 1000$) 문니를 내고 정점 $v$에 인접한 포털 목록을 원하는 순서로 바꿀 수 있다. 그 후에는 목록의 처음 두 포털이 짝지어지고, 마지막 두 포털도 짝지어진다.

예를 들어 정점 $v$에 인접한 포털을 $\[p\_{v,3},p\_{v,1},p\_{v,2},p\_{v,4}]$ 순서로 바꾸면, 정점 $v$에서 다음과 같이 동작한다.

• 현재 포털 $p\_{v,1}$에 있다면 포털 $p\_{v,3}$으로 전환할 수 있고, 그 반대도 가능하다.
• 현재 포털 $p\_{v,2}$에 있다면 포털 $p\_{v,4}$로 전환할 수 있고, 그 반대도 가능하다.
• 더 이상 포털 $p\_{v,1}$에서 $p\_{v,2}$로, 또는 포털 $p\_{v,3}$에서 포털 $p\_{v,4}$로 전환할 수 없다.

모든 위치에서 다른 모든 위치로 도달할 수 있도록 네트워크를 수정하는 데 필요한 최소 총 문니를 구하라. 테스트 데이터는 네트워크를 유효하게 수정하는 방법이 적어도 하나 존재하도록 주어진다.

첫째 줄에 $N$이 주어진다.

다음 $N$개의 줄이 각 정점을 설명한다. $v+1$번째 줄에는 공백으로 구분된 다섯 정수 $c\_v,p\_{v,1},p\_{v,2},p\_{v,3},p\_{v,4}$가 주어진다.

각 $v$에 대해 $p\_{v,1},p\_{v,2},p\_{v,3},p\_{v,4}$는 모두 서로 다르며, 모든 포털은 정확히 두 정점의 인접 목록에 나타난다.

모든 위치에서 다른 모든 위치로 도달할 수 있도록 네트워크를 수정하는 데 필요한 최소 총 문니를 한 줄에 출력한다.

정점 $1$과 $4$의 인접 목록만 바꾸면 된다. 이때 총 $c\_1+c\_4=13$ 문니가 필요하다. $p\_1=\[1,9,4,8]$, $p\_4=\[7,4,6,3]$로 두면 된다.