삼각 그래프

삼각 그래프는 사이클이 없는 방향 그래프로, $N \ge 2$개의 행과 $3$개의 열로 이루어진다. 열은 왼쪽부터 $1$번(왼쪽), $2$번(가운데), $3$번(오른쪽)이라 부르고, $i$번째 행 $j$번째 열의 정점을 $(i, j)$로 나타낸다.

보통의 그래프와 달리 비용은 간선이 아니라 정점에 있다. 어떤 경로의 비용은 그 경로가 지나간 모든 정점의 비용을 더한 값이다.

목표는 가장 위쪽 가운데 정점 $(1, 2)$에서 가장 아래쪽 가운데 정점 $(N, 2)$로 가는 최소 비용 경로를 찾는 것이다.

삼각 그래프의 방향 간선은 항상 다음과 같이 연결되어 있다.

• 같은 행 안에서: 모든 행 $i$에 대해 $(i, 1) \to (i, 2)$와 $(i, 2) \to (i, 3)$.
• 다음 행으로: $1 \le i < N$을 만족하는 모든 행 $i$에 대해
  • $(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)$

예를 들어 가운데 열의 비용이 위에서부터 $7, 13, 3, 6$인 그래프에서, 아래로만 내려가는 경로 $(1,2) \to (2,2) \to (3,2) \to (4,2)$의 비용은 $7 + 13 + 3 + 6 = 29$이다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 $N$이 주어진다 $(2 \le N \le 100{,}000)$. 이어지는 $N$개의 줄에는 각 행에 있는 세 정점의 비용이 왼쪽, 가운데, 오른쪽 순서로 주어진다. 모든 비용은 정수이며, 각 비용의 제곱은 $1{,}000{,}000$보다 작다. (따라서 비용은 음수일 수도 있다.)

입력의 마지막 줄에는 입력의 끝을 나타내는 $0$이 하나 주어진다.

각 테스트 케이스마다 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 아래 형식에 맞춰 한 줄에 출력한다.

k. n

여기서 $k$는 테스트 케이스 번호($1$부터 시작)이고, $n$은 그 테스트 케이스의 최소 비용이다.