Triangle Graph

A triangle graph is a directed acyclic graph made of $N \ge 2$ rows and $3$ columns. Number the columns $1$ (left), $2$ (center), and $3$ (right), and write $(i, j)$ for the vertex in column $j$ of row $i$.

Unlike an ordinary graph, the cost lives on the vertices, not the edges. The cost of a path is the sum of the costs of every vertex it passes through.

The goal is to find the minimum-cost path from the top-center vertex $(1, 2)$ to the bottom-center vertex $(N, 2)$.

The directed edges of a triangle graph are always connected as follows.

• Within a row: for every row $i$, $(i, 1) \to (i, 2)$ and $(i, 2) \to (i, 3)$.
• To the next row: for every row $i$ with $1 \le i < N$,
  • $(i, 1) \to (i+1, 1)$, $(i, 1) \to (i+1, 2)$
  • $(i, 2) \to (i+1, 1)$, $(i, 2) \to (i+1, 2)$, $(i, 2) \to (i+1, 3)$
  • $(i, 3) \to (i+1, 2)$, $(i, 3) \to (i+1, 3)$

For example, in a graph whose center-column costs are $7, 13, 3, 6$ from top to bottom, the straight-down path $(1,2) \to (2,2) \to (3,2) \to (4,2)$ costs $7 + 13 + 3 + 6 = 29$.

The input consists of several test cases.

The first line of each test case contains the number of rows $N$ $(2 \le N \le 100{,}000)$. Each of the next $N$ lines contains the costs of the three vertices in that row, in left, center, right order. Every cost is an integer, and the square of each cost is less than $1{,}000{,}000$ (so a cost may be negative).

The last line of the input contains a single $0$, marking the end of the input.

For each test case, print on one line the minimum cost of a path from the top-center vertex to the bottom-center vertex, in the following format.

k. n

Here $k$ is the test case number (starting from $1$) and $n$ is the minimum cost for that test case.