Haywire

Farmer John's $N$ cows ($4 \le N \le 12$, $N$ even) have built a primitive system for communicating between pairs of friendly cows: each friendly pair is joined by a wire wrapped in hay.

Each cow has exactly 3 friends, and the cows arrange themselves to occupy $N$ stalls lined up in a single row, one cow per stall. A wire of length $L$ requires exactly $L$ units of hay to build; for example, if the cows in stalls 4 and 7 are friends, the wire connecting them takes $3$ units of hay.

Every pair of friends must be connected by a separate wire. Determine the minimum possible total amount of hay required if the cows order themselves in the best possible way.

• Line 1: the integer $N$. The cows are numbered $1$ through $N$.
• Lines 2 through $N+1$: line $i+1$ contains three space-separated integers in the range $1$ to $N$, the three friends of cow $i$. If cow $i$ is a friend of cow $j$, then cow $j$ is also a friend of cow $i$.

• Line 1: the minimum total amount of hay required to connect all pairs of friendly cows.

Consider the case of 6 cows. Cow 1 is friends with cows 6, 2, and 5, and the rest are given similarly. Ordering the cows as $6, 5, 1, 4, 2, 3$ is optimal and requires only $17$ units of hay.