#include <stdio.h>
#include <algorithm>

using namespace std;

struct matrix {
	int a[60][60];
} ini , pw;
int n , m , q;
int dis[120][120];
int ans;
void clear () {
}
matrix operator * ( matrix x1 , matrix x2 ) {
	int i , j , k;
	matrix y;
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			y.a[i][j] = -1;
		}
	}
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			for ( k = 1 ; k <= n ; k++ ) {
				if ( x1.a[i][j] != -1 && x2.a[j][k] != -1 ) {
					if ( y.a[i][k] == -1 ) y.a[i][k] = x1.a[i][j] + x2.a[j][k];
					else y.a[i][k] = min ( y.a[i][k] , x1.a[i][j] + x2.a[j][k] );
				}
			}
		}
	}
	return y;
}
matrix ksm ( matrix f , int x ) {
	matrix s;
	int i , j;
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			s.a[i][j] = -1;
		}
		s.a[i][i] = 0;
	}
	while ( x ) {
		if ( x % 2 == 1 ) s = s * f;
		f = f * f; x = x / 2;
	}
	return s;
}
void work () {
	int i , j , k , u , v , w;
	int s , t;
	scanf ( "%d%d" , &n , &m );
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			dis[i][j] = -1;
		}
	}
	for ( i = 1 ; i <= m ; i++ ) {
		scanf ( "%d%d%d" , &u , &v , &w );
		if ( dis[u][v] == -1 ) dis[u][v] = w;
		else dis[u][v] = min ( dis[u][v] , w );
	}
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			ini.a[i][j] = dis[i][j];
		}
	}
	for ( i = 1 ; i <= n ; i++ ) {
		dis[i][i] = 0;
	}
	for ( k = 1 ; k <= n ; k++ ) {
		for ( i = 1 ; i <= n ; i++ ) {
			for ( j = 1 ; j <= n ; j++ ) {
				if ( dis[i][k] != -1 && dis[k][j] != -1 ) {
					if ( dis[i][j] == -1 ) dis[i][j] = dis[i][k] + dis[k][j];
					else dis[i][j] = min ( dis[i][j] , dis[i][k] + dis[k][j] );
				}
			}
		}
	}
	scanf ( "%d" , &q );
	for ( i = 1 ; i <= q ; i++ ) {
		scanf ( "%d%d%d" , &s , &t , &k );
		pw = ksm ( ini , k );
		ans = -1;
		for ( j = 1 ; j <= n ; j++ ) {
			if ( pw.a[s][j] != -1 && dis[j][t] != -1 ) {
				if ( ans == -1 ) ans = pw.a[s][j] + dis[j][t];
				else ans = min ( ans , pw.a[s][j] + dis[j][t] );
			}
		}
		printf ( "%d\n" , ans );
	}
}
int main () {
	int t;
	scanf ( "%d" , &t );
	while ( t-- ) {
		work ();
		clear ();
	}
	return 0;
}