#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<cassert>
#include<algorithm>
#include<functional>
#include<ctime>
using namespace std ;
ifstream fin("hardest.in") ;
ofstream fout("hardest.out") ;
const int maximum = 0x7ffffff ;
int T , path[10001][10001] , m , n ;
void init( void ) ;
int Floyd( void ) ;
int main()
{
	fin >> T ; 
	while (T--)
	{
		memset( path , -1 , sizeof(path)) ;
		fin >> n >> m ;
		for ( int h = 1 ; h <= m ; h ++ )
		{
			int i , j , k , minimum = 0x7ffffff ;
			fin >> i >> j ;
			for ( int oi = 1 ; oi <= m ; oi ++)
			{ fin >> k ; minimum = min( k , minimum ) ; }
			path[ i ][ j ] = path[ j ][ i ] = minimum ;
		}
		fout << Floyd() << endl ;
	}
	return 0 ;
}
int Floyd( void )
{
	for ( int k = 1 ; k <= m ; k ++)
	{
		for ( int i = 1 ; i <= m ; i ++)
		{
			for ( int j = 1 ; j <= m ; j ++)
			{
				if ( ( ( path[ i ][ k ] + path[ k ][ j ] ) < path[ i ][ j ] && path[ i ][ k ] && path[ k ][ j ] ) || path[ i ][ j ] == 0 )
				{
					path[ i ][ j ] = path[ i ][ k ] + path[ k ][ j ] ;
				}
				else return -1 ;
			}
		}
	}
	return path[ 1 ][ n ] ;
}