#include<cstdio>#include<cstring>#include<iostream>#include<vector>#include<algorithm>const int inf = 9999999;using namespace std;vector<int> g;int cnt,n,fans;int map[1100][1100],fa[1010],d[1100],pt[110];void init(){ cnt=0; fans=0; for(int i=0;i<n;i++) fa[i]=i;}int find(int x){ return fa[x]!=x?fa[x]=find(fa[x]):x;}void Union(int a,int b){ int f1=find(a),f2=find(b); if(f1!=f2) fa[f1]=f2;}void floyd(){ int sz=g.size(); for(int k=0;k<sz;k++) for(int i=0;i<sz;i++) for(int j=0;j<sz;j++) map[g[i]][g[j]]=min(map[g[i]][g[j]],map[g[i]][g[k]]+map[g[k]][g[j]]);}int brute(int x){ int ans=0; int sz=g.size(); for(int i=0;i<sz;i++) if(map[x][g[i]]!=inf) ans=max(ans,map[x][g[i]]); return ans;}void solve(){ for(int i=0;i<cnt;i++) { int ans=inf; g.clear(); for(int j=0;j<n;j++) if(fa[j]==pt[i]) g.push_back(j); floyd(); int sz=g.size(); for(int j=0;j<sz;j++) { ans=min(ans,brute(g[j])+d[g[j]]); } fans=max(fans,ans); }}int main(){ while(~scanf("%d",&n)) { init(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { scanf("%d",&map[i][j]); if(map[i][j]!=0 && map[i][j]!=-1) Union(i,j); if(map[i][j]==-1) map[i][j]=inf; } for(int i=0;i<n;i++) scanf("%d",&d[i]); for(int i=0;i<n;i++) if(fa[i]==i) { pt[cnt++]=fa[i]; } floyd(); solve(); printf("%dn",fans); } return 0;}
