#ifndef davele
#include "towns.h"
#endif // davele
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int lim = 120, limit = lim +5;
template <class X, class Y>
bool minimize (X&x, const Y&y){
if (x<=y) return false;
x = y;
return true;
}
template <class X, class Y>
bool maximize (X&x, const Y&y){
if (x>=y) return false;
x = y;
return true;
}
//////////////////////////////////
int dist1[limit], dist2[limit];
int incen[limit];
int distcen[limit];
int sz[limit], par[limit];
mt19937_64 rng (chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef davele
int n, dd[limit][limit];
int getDistance (int u, int v){
// cerr<<u<<" "<<v<<"\n";
return dd[u][v];
}
#endif // davele
int finds (int u){
if (u==par[u]) return u;
return par[u] = finds (par[u]);
}
bool unions (int u, int v){
int a = finds (u), b = finds (v);
if (a==b) return false;
if (sz[a]<sz[b]) swap(a, b);
sz[a]+=sz[b];
par[b] = a;
return true;
}
void matching (int u, int v){
if (incen[u]>0 || incen[v]>0){
if (incen[u]==incen[v]){
unions (u, v);
}
}
else if (distcen[u]+distcen[v]>getDistance(u, v)){
unions (u, v);
}
}
void shrink (vector <int>&can){
if (can.size()%2==1){
can.pop_back();
return;
}
vector <int> rem;
for (int i=0; i<can.size(); i+=2){
int u = can[i], v = can[i+1];
// cerr<<u<<" "<<v<<"\n";
if (incen[u]>0 || incen[v]>0){
if (incen[u]==incen[v]){
unions (u, v);
rem.pb(u);
}
}
else if (distcen[u]+distcen[v]>getDistance(u, v)){
unions (u, v);
rem.pb(u);
}
}
can = rem;
}
int hubDistance(int N, int sub){
int mut1 = 0;
int d1 = 0;
for (int i=1; i<N; i++){
int tmp = getDistance (0, i);
if (maximize (d1, tmp)){
mut1 = i;
}
}
int mut2 = mut1;
dist1[mut1] = 0;
int d2 = 0;
for (int i=0; i<N; i++){
if (i==mut1) continue;
int tmp = getDistance (mut1, i);
dist1[i] = tmp;
if (maximize (d2, tmp)){
mut2 = i;
}
}
//
dist2[mut2] = 0;
for (int i=0; i<N; i++) if (i!=mut2) dist2[i] = getDistance(mut2, i);
//
// phase 1: Find R
int R = dist1[mut2];
int cen = mut1;
for (int i=0; i<N; i++){
int cur = (dist1[i]+dist2[i]-dist1[mut2])/2;
if (minimize (R, max(dist1[i], dist2[i])-cur)){
cen = i;
}
}
//
int cen2 = -1;
for (int i=0; i<N; i++){
if (i==cen) continue;
int cur = (dist1[i]+dist2[i]-dist1[mut2])/2;
if (max(dist1[i], dist2[i])-cur==R){
cen2 = i;
break;
}
}
//
for (int i=0; i<N; i++){
incen[i] = 0;
}
int cnt1 = 0, cnt2= 0;
for (int i=0; i<N; i++){
int cur = (dist1[i]+dist2[i]-dist1[mut2])/2;
int curcen = (dist1[cen]+dist2[cen]-dist1[mut2])/2;
if (dist1[i]-cur<dist1[cen]-curcen){
incen[i] = 1;
cnt1++;
}
else if ((dist1[i]-cur)>(dist1[cen]-curcen)){
incen[i] = 2;
cnt2++;
}
else{
incen[i] = 0;
distcen[i] = cur;
}
}
if (cnt1*2>N || cnt2*2>N){
if (cen2==-1) return -R;
swap(cen, cen2);
for (int i=0; i<N; i++){
incen[i] = false;
}
cnt1 = 0; cnt2= 0;
for (int i=0; i<N; i++){
int cur = (dist1[i]+dist2[i]-dist1[mut2])/2;
int curcen = (dist1[cen]+dist2[cen]-dist1[mut2])/2;
if (dist1[i]-cur<dist1[cen]-curcen){
incen[i] = 1;
cnt1++;
}
else if ((dist1[i]-cur)>(dist1[cen]-curcen)){
incen[i] = 2;
cnt2++;
}
else{
incen[i] = 0;
distcen[i] = cur;
}
}
if (cnt1*2>N || cnt2*2>N) return -R;
}
// cerr<<cen<<"\n";
// for (int i=0; i<N; i++){
// cerr<<i<<" "<<incen[i]<<" "<<distcen[i]<<"\n";
// }
vector <int> candidate;
for (int i=0; i<N; i++){
candidate.pb(i);
par[i] = i;
sz[i] = 1;
}
shuffle (candidate.begin(), candidate.end(), rng);
while (candidate.size()>1){
shrink(candidate);
}
//
if (candidate.empty()) return R;
for (int i=0; i<N; i++) if (finds(i)!=finds(candidate[0]) && i==finds(i)){
matching(i, candidate[0]);
}
for (int i=0; i<N; i++){
if (sz[finds(i)]*2>N) return -R;
}
return R;
}
#ifdef davele
signed main(){
freopen("towns.in", "r", stdin);
freopen("towns.out", "w", stdout);
int t1, t2;
cin>>t1>>t2;
cin>>n;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) cin>>dd[i][j];
cout<<hubDistance(n, t1);
}
#endif // davele
