/**********************************************************************
 * 
 * If we had all the shortest distances between the pairs of distinct
 * sites then our task would be very easy, just sort them and look at
 * the right position.
 * 
 * So how do we compute the shortest path from each site to every other
 * site? This can easily be done using the Floyd-Warshall algorithm
 * that you'll find in any good general algorithm book, probably in a
 * "shortest paths" chapter. The basic idea is as follows: Start with
 * a distance matrix so that dist[i][j] is the length of the direct
 * connection (an edge in the graph) from i to j, or infinity if there's
 * no direct connection. The matrix now represents all shortest distances
 * for paths that are only direction connections, not going through
 * intermediate sites. Now we successively improve the matrix entries,
 * allowing more and more sites to be intermediate sites on paths.
 * If we allow site k to be an intermediate site in paths, then for
 * an entry dist[i][j] we either keep the old value or we use
 * dist[i][k] + dist[k][j], whatever is smaller. The latter represents
 * going from i to k and then (from k) to j.
 * 
 * As mentioned above, you'll easily find more detailed descriptions in
 * good books (or on the web, of course). Just one implementation detail:
 * I represent infinity here as a large finite value. At the beginning,
 * -1 distances that represent "no direct connection" are turned into
 * a large value by "anding" them with 0xFFFFFFF
 * 
 **********************************************************************/

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int SC;
  cin >> SC;
  for( int S=1; S<=SC; S++ ){
    cout << "Scenario #" << S << ":" << endl;
    
    //--- Read the testcase.
    int p, n, dist[100][100];
    cin >> p >> n;
    for( int i=0; i<n; i++ ){
      for( int j=0; j<n; j++ ){
	cin >> dist[i][j];
	dist[i][j] &= 0xFFFFFFF;
      }
    }
    
    //--- Dance the funky Floyd-Warshall...
    for( int k=0; k<n; k++ )
      for( int i=0; i<n; i++ )
	for( int j=0; j<n; j++ )
	  dist[i][j] = dist[i][j] < dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];
    
    //--- Collect and sort all distances.
    int all[10000], m = 0;
    for( int i=0; i<n; i++ )
      for( int j=0; j<n; j++ )
	if( i != j )
	  all[m++] = dist[i][j];
    sort( all, all+m );
    
    //--- Answer.
    cout << all[ (p * m + 99) / 100 - 1 ] << endl << endl;
  }
}
