SP7975 ACPC10D - Tri graphs

这是一个简洁的图论问题：在给定的三列图中，找到从最上面的那一行中间顶点开始，到最下面一行中间顶点的最短路径。三列图是一个无环图，包含 $N \ge 2$ 行和固定的三列。在这个图中，与常规图不同的是，费用是和顶点关联的，而不是和边关联的。 例如，当 $N = 4$ 时，沿着中间顶点直接从上到下行走的费用是 $7 + 13 + 3 + 6 = 29$。图中有向边的排列始终如图所示。

程序将处理一个或多个测试用例。 每个测试用例由 $N + 1$ 行组成，其中第一行包含一个整数 $N$（$2 < N \le 100000$），接下来的 $N$ 行每行有三个整数，分别表示该行的三个顶点的费用。输入以一个零作为结束标志。

对于每个测试用例，输出以下格式的结果： ``` k. n ``` 其中 $k$ 是测试用例的编号（从 1 开始），$n$ 是从顶行中间顶点到底行中间顶点的最小费用。

- $2 < N \le 100000$ - 每个顶点的费用都是非负整数。 **本翻译由 AI 自动生成**