//Accepted 320 KB 16 ms
//有n个顶点,边权用A表示
//给出下三角矩阵,求从一号顶点出发到各点的最短路的最大值
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
/**
* This is a documentation comment block
* 如果有一天你坚持不下去了,就想想你为什么走到这儿!
* @authr songt
*/
;
const int imax_e = imax_n*imax_n;
;
struct node
{
int u,v,c;
node(,,):u(u),v(v),c(c)
{
}
}p[imax_e];
int head[imax_n];
int next[imax_e];
bool vis[imax_n];
int dis[imax_n];
int cnt[imax_n];
int n;
;
void init()
{
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
e=;
}
void addEdge(int u,int v,int c)
{
p[e]=node(u,v,c);
next[e]=head[u];
head[u]=e++;
}
bool relax(int u,int v,int c)
{
if (dis[v]>dis[u]+c)
{
dis[v]=dis[u]+c;
return true;
}
return false;
}
queue<int > q;
bool spfa(int src)
{
while (!q.empty()) q.pop();
memset(vis,,sizeof(vis));
memset(cnt,,sizeof(cnt));
;i<=n;i++)
dis[i]=inf;
dis[src]=;
q.push(src);
vis[src]=;
cnt[src]++;
while (!q.empty())
{
int pre=q.front();
q.pop();
vis[pre]=;
;i=next[i])
{
if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v])
{
if ((++cnt[p[i].v])>=n) return false;
vis[p[i].v]=;
q.push(p[i].v);
}
}
}
return true;
}
];
int main()
{
while (scanf("%d",&n)!=EOF)
{
init();
;i<=n;i++)
{
;j<i;j++)
{
scanf("%s",s);
]=='x') continue;
int c=atoi(s);
//printf("c=%d\n",c);
addEdge(i,j,c);
addEdge(j,i,c);
}
}
spfa();
;
;i<=n;i++)
if (dis[i]>ans) ans=dis[i];
printf("%d\n",ans);
}
;
}