#include<iostream>
#include<queue>
#include<cstdlib>
#include<cstring>
using namespace std;
#define p1 pair<int,p2>
#define p2 pair<int,int>
#define x second.first
#define y second.second
#define cost first
int main()
{
//priority_queue<p1>q;
priority_queue<p1,vector<p1>,greater<p1> >q;
int n,i,j,k=1;
int dx[]={1,1,0,1};
int dy[]={0,1,1,-1};
while(1)
{
cin>>n;
if(n==0)
break;
int c[n+10][n+10];
int vis[n+10][n+10];
for(i=0;i<n;i++)
{
for(j=0;j<3;j++)
{
cin>>c[i][j];
}
}
q.push(p1(c[0][1],p2(0,1)));
memset(vis,0,sizeof(vis));
while(!q.empty())
{
p1 temp=q.top();
q.pop();
// cout<<" x "<<temp.x<<" y "<<temp.y<<" "<<temp.cost<<endl;
vis[temp.x][temp.y]=1;
if(temp.x==n-1 && temp.y==1)
{
cout<<k<<". "<<temp.cost<<endl;
break;
}
for(i=0;i<4;i++)
{
int nx= temp.x+dx[i];
int ny=temp.y+dy[i];
if(nx<=n-1&&nx>=0&&ny<=2&&ny>=0&&!vis[nx][ny])
{
//cout<<" cost "<<temp.cost<< " "<<c[nx][ny]<<endl;
q.push(p1((temp.cost+c[nx][ny]),p2(nx,ny)));
}
}
}
k++;
}
return 0;
}
CgoKI2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxjc3RkbGliPgojaW5jbHVkZTxjc3RyaW5nPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgcDEgcGFpcjxpbnQscDI+CiNkZWZpbmUgcDIgcGFpcjxpbnQsaW50PgojZGVmaW5lIHggIHNlY29uZC5maXJzdAojZGVmaW5lIHkgIHNlY29uZC5zZWNvbmQKI2RlZmluZSAgICBjb3N0IGZpcnN0CgppbnQgbWFpbigpCnsKICAgLy9wcmlvcml0eV9xdWV1ZTxwMT5xOwogICBwcmlvcml0eV9xdWV1ZTxwMSx2ZWN0b3I8cDE+LGdyZWF0ZXI8cDE+ID5xOwoKICAgIGludCBuLGksaixrPTE7CiAgICBpbnQgZHhbXT17MSwxLDAsMX07CiAgICBpbnQgZHlbXT17MCwxLDEsLTF9OwogICAgd2hpbGUoMSkKICAgIHsKICAgIGNpbj4+bjsKICAgIGlmKG49PTApCiAgICAgICAgYnJlYWs7CiAgICBpbnQgY1tuKzEwXVtuKzEwXTsKICAgIGludCB2aXNbbisxMF1bbisxMF07CiAgICBmb3IoaT0wO2k8bjtpKyspCiAgICB7CiAgICAgICAgZm9yKGo9MDtqPDM7aisrKQogICAgICAgIHsKCiAgICAgICAgY2luPj5jW2ldW2pdOwoKICAgICAgICB9CgogICAgfQogICAgcS5wdXNoKHAxKGNbMF1bMV0scDIoMCwxKSkpOwogICAgbWVtc2V0KHZpcywwLHNpemVvZih2aXMpKTsKICAgICAgIHdoaWxlKCFxLmVtcHR5KCkpCgp7CiAgICBwMSB0ZW1wPXEudG9wKCk7CiAgICBxLnBvcCgpOwogICAvLyBjb3V0PDwiIHggIjw8dGVtcC54PDwiIHkgIjw8dGVtcC55PDwiICI8PHRlbXAuY29zdDw8ZW5kbDsKICAgIHZpc1t0ZW1wLnhdW3RlbXAueV09MTsKCiAgICBpZih0ZW1wLng9PW4tMSAmJiB0ZW1wLnk9PTEpCiAgICB7CiAgICAgICAgY291dDw8azw8Ii4gIjw8dGVtcC5jb3N0PDxlbmRsOwogICAgICAgIGJyZWFrOwogICAgfQogICAgZm9yKGk9MDtpPDQ7aSsrKQogICAgewogICAgICAgIGludCBueD0gdGVtcC54K2R4W2ldOwogICAgICAgIGludCBueT10ZW1wLnkrZHlbaV07CgogICAgICAgIGlmKG54PD1uLTEmJm54Pj0wJiZueTw9MiYmbnk+PTAmJiF2aXNbbnhdW255XSkKICAgICAgICB7CiAgICAgICAgICAgIC8vY291dDw8IiBjb3N0ICI8PHRlbXAuY29zdDw8ICIgIjw8Y1tueF1bbnldPDxlbmRsOwogICAgICAgICAgICBxLnB1c2gocDEoKHRlbXAuY29zdCtjW254XVtueV0pLHAyKG54LG55KSkpOwogICAgICAgIH0KCiAgICB9CgoKfQprKys7CgogICAgfQoKICAgIHJldHVybiAwOwp9Cg==