#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

static const int INF = 0x3fffffff;

class TaxiManager { public:
	int schedule(vector <string> roads, vector <string> customers) 
	{
		const int V = roads.size();
		vector< vector<int> > d(V, vector<int>(V));
		for(int i=0; i<V; ++i)
			for(int j=0; j<V; ++j)
				if( i != j )
					d[i][j] = (roads[i][j]=='0' ? INF : roads[i][j]-'0');
		for(int k=0; k<V; ++k)
			for(int i=0; i<V; ++i)
				for(int j=0; j<V; ++j)
					d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

		const int M = customers.size();
		vector< pair<int,int> > c;
		for(int i=0; i<M; ++i)
		{
			int f, t;
			stringstream(customers[i]) >> f >> t;
			c.push_back( make_pair(f,t) );
		}

		int best = INF;
		for(int mask=0; mask<(1<<M); ++mask)
			best = min(best, max(tsp(d,c,mask), tsp(d,c,((1<<M)-1)&~mask)));
		return best;
	}

	map<pair<int,int>, int> memo;
	int tsp(const vector< vector<int> >& d, const vector< pair<int,int> >& c, int mask, int cur=0)
	{
		if( mask == 0 )
			return d[cur][0];

		pair<int,int> key(mask, cur);
		if( memo.count(key) ) return memo[key];

		int best = INF;
		for(int next=0; (1<<next)<=mask; ++next)
			if( (1<<next) & mask )
				best = min(best,
					d[cur][c[next].first] + d[c[next].first][c[next].second] + tsp(d,c,mask&~(1<<next),c[next].second));
		return memo[key] = best;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, TaxiManager().schedule(roads, customers));}
int main(){

CASE(0)
	string roads_[] = {"020200"
,"202020"
,"020002"
,"200020"
,"020202"
,"002020"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	string customers_[] = {"5 3","2 4","1 5","3 2"};
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	int _ = 16; 
END
CASE(1)
	string roads_[] = 
{"00020251090265906661"
,"00763002550100090081"
,"06003699000080062771"
,"00000710460400035310"
,"50000039119198350060"
,"66060004050810046028"
,"02333108565000200880"
,"40212560000209205231"
,"02601150098329905062"
,"00210383709951005203"
,"10111087340780827070"
,"05065800003095040140"
,"15604020082000100090"
,"83430030070580600750"
,"10588355007006001150"
,"14400080790005400536"
,"23400990400933060004"
,"11053016300602000090"
,"90040920084059282502"
,"61300007077904050900"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	string customers_[] = {"0 19","4 16","15 16","4 18","2 7","9 15","11 6","7 13","19 13","12 19","14 12","16 1"};
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	int _ = 33; 
END
CASE(2)
	string roads_[] = 
{"095222800320504"
,"107600288090501"
,"760973530769345"
,"963093337510830"
,"338404069255826"
,"291700050155264"
,"002783031709004"
,"404730701707712"
,"068870030090995"
,"320025180036103"
,"468695042801904"
,"233626561000105"
,"070014432197086"
,"887301000143802"
,"230852749990330"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	string customers_[] = {"3 6","0 4","2 7","9 7","13 9","1 6","7 13","14 2","8 7","10 1","11 13","7 12"};
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	int _ = 28; 
END
CASE(3)
	string roads_[] = {"00401","50990","00062","08008","03000"};
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	string customers_[] = {"2 4"};
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	int _ = 14; 
END
/*
CASE(4)
	string roads_[] = ;
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	string customers_[] = ;
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	int _ = ; 
END
CASE(5)
	string roads_[] = ;
	  vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 
	string customers_[] = ;
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	int _ = ; 
END
*/
}
// END CUT HERE
