Problem E
Finding Laputa

the ancient city of Laputa

Pazu and Sheeta are on their quest to the island of Laputa, an ancient floating city shrouded in mystery. Sheeta’s crystal necklace reveals a complex network resembling a hypercube — a mathematical structure they need to navigate to reach Laputa sooner.

The hypercube is an $n$-dimensional hypercube of side-length $1$ with a diagonal from $O=(0,0,\dots ,0)$ to $E=(1,1,\dots ,1)$. (That is, its vertices are exactly all $(x_1,\dots ,x_n)$ with $x_i\in \{ 0,1\} $.) Vertex $O$ turns out to be Pazu and Sheeta’s current location, and vertex $E$ is where Laputa is located. Each edge is undirected and is assigned an integer weight $w_i$ denoting the time cost to travel through that edge. The total time to go from $A$ to $B$ is the minimal sum of all weights along a path from $A$ to $B$.

However, the journey is not simple as Pazu and Sheeta are under the pressure to reach Laputa before the military airship Goliath. Thankfully, they can use the crystal necklace to instantly create new additional undirected edges between certain vertices of the hypercube. They may add as many edges as they want to connect any two vertices that are nonadjacent and well-ordered. Here, two vertices $(a_1,\dots ,a_n)$ and $(b_1,\dots ,b_n)$ are said to be well-ordered if either $a_1\leq b_1,\dots ,a_n\leq b_n$ or $a_1\ge b_1,\dots ,a_n\ge b_n$. The weight of an added edge between two vertices equals the square of the number of positions where their coordinates differ.

For example, if $n = 4$, then

• The edge that connects $(1,0,1,1)$ to $(1,0,0,0)$ should have weight $4$.

• The necklace can’t connect $(1,0,1,0)$ to $(1,0,1,1)$ because they are adjacent.

• The necklace can’t connect $(1,0,1,1)$ to $(1,1,0,1)$ because they are not well-ordered.

What is the shortest possible time for Pazu and Sheeta to travel from $O$ to $E$?

For the sake of simpler inputs, let’s just use binary to represent coordinates. For example, $(0,1,0,1)$ is equivalent to $0101_2=5$.

Input

The first line contains an integer $n \: (3\leq n\leq 15)$ denoting the dimension of the hypercube.

Each of the next $n \cdot 2^{n-1}$ lines contains an integer $i \: (0\leq i<2^n)$ denoting the coordinate of vertex $A$, an integer $j \: (0\leq j<2^n)$ denoting the coordinate of vertex $B$, and an integer $w \: (1\leq w\leq 5)$ denoting the weight of the edge connecting $A$ and $B$.

It is guaranteed that each edge is assigned one (and only one) weight.

Output

Output two lines. The first line contains the minimal time to travel from $O$ to $E$. The second line contains the least number of edges Pazu and Sheeta need to add in order to minimize the distance between $O$ and $E$.

3
0 1 2
0 2 5
0 4 3
1 3 3
1 5 4
2 3 5
2 6 3
3 7 3
4 5 4
4 6 5
5 7 4
6 7 5

6
1