古老的城市拉普达

巴鲁（Pazu）和希达（Sheeta）正在寻找传说中神秘的漂浮岛屿——天空之城拉普达（Laputa）。希达的水晶项链显现出了一个类似于超立方体的复杂网络——这是一个他们需要穿过的数学结构，以便更快地到达拉普达。

该超立方体是一个边长为 1 的 $n$ 维超立方体，其对角线从 $O = (0, 0, \dots, 0)$ 延伸到 $E = (1, 1, \dots, 1)$。（也就是说，它的顶点恰好是所有满足 $x_i \in \{0, 1\}$ 的 $(x_1, \dots, x_n)$。）顶点 $O$ 是巴鲁和希达当前所在的位置，而顶点 $E$ 是拉普达所在的位置。每条边都是无向的，并被赋予了一个整数边权 $w_i$，表示通过该边所需的时间。

从 $A$ 到 $B$ 的总时间是从 $A$ 到 $B$ 的路径上所有边权之和的最小值。

然而，旅程并不简单，因为巴鲁和希达面临着在军用飞艇歌利亚号（Goliath）之前到达拉普达的压力。幸运的是，他们可以使用水晶项链在超立方体的某些顶点之间瞬间创建新的无向边。他们可以添加任意数量的边，来连接任意两个不相邻且良序（well-ordered）的顶点。这里，如果两个顶点 $(a_1, \dots, a_n)$ 和 $(b_1, \dots, b_n)$ 满足 $a_1 \le b_1, \dots, a_n \le b_n$ 或 $a_1 \ge b_1, \dots, a_n \ge b_n$，则称它们是良序的。在两个顶点之间添加的边的权重等于它们坐标不同的位置数量的平方。

例如，如果 $n = 4$，那么：

• 连接 $(1, 0, 1, 1)$ 和 $(1, 0, 0, 0)$ 的边权重应为 4。
• 项链不能连接 $(1, 0, 1, 0)$ 和 $(1, 0, 1, 1)$，因为它们是相邻的。
• 项链不能连接 $(1, 0, 1, 1)$ 和 $(1, 1, 0, 1)$，因为它们不是良序的。

巴鲁和希达从 $O$ 旅行到 $E$ 的最短可能时间是多少？

为了简化输入，我们使用二进制来表示坐标。例如，$(0, 1, 0, 1)$ 等价于 $0101_2 = 5$。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 15$)，表示超立方体的维度。

接下来的 $n \cdot 2^{n-1}$ 行中，每行包含一个整数 $i$ ($0 \le i < 2^n$) 表示顶点 $A$ 的坐标，一个整数 $j$ ($0 \le j < 2^n$) 表示顶点 $B$ 的坐标，以及一个整数 $w$ ($1 \le w \le 5$) 表示连接 $A$ 和 $B$ 的边的权重。

保证每条边都被赋予了唯一的一个权重。

输出格式

输出两行。第一行包含从 $O$ 到 $E$ 旅行的最短时间。第二行包含为了使 $O$ 和 $E$ 之间的距离最小，巴鲁和希达需要添加的最少边数。

样例

输入样例 1

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

输出样例 1

6
1