Byteasar 是 Byteoian Railways 的一名便衣巡视员。BR 的铁路架构是一棵 个节点的树，Byteasar 需要检查所有的N个节点。他按照如下方式行动：
首先选定一个行动中心 ，并且检查 。
从 出发前往任意一个未检查的点（沿树上两点的唯一最短路走），检查该节点，然后返回 。特别地，检查完最后一个节点后不需要返回。
检查节点不需要时间，走过一条路的时间为 。
为了不暴露身份，Byteasar 规定相邻两次检查所经过的道路不允许有重复。
也就是说，除第一次检查之外，他每次从 出发走过的第一条边不能和上一次出发相同。
第一行是一个整数 。
接下来 行每行有 个整数 ，表示 和 之间有一条边。
行，第 行表示如果以 作为行动中心，Byteasar 检查完所有车站需要的最小时间。如果不可能做到，该行输出 。
9 3 6 2 4 2 6 2 5 1 7 2 7 8 9 7 8
-1 23 -1 -1 -1 -1 -1 -1 -1
对于 的数据，。
对于 的数据，，。
鸣谢 Object022。
