#pragma GCC optimize(3)

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

using namespace std;

struct matrix {
	int n , m;
	int a[51][51];
} ini[120] , ini100[120] , now;
int n , m , q;
int dis[120][120];
int ans;
void clear () {
}
matrix operator * ( matrix &x1 , matrix &x2 ) {
	int i , j , k;
	matrix y;
	y.n = x1.n; y.m = x2.m;
	for ( i = 1 ; i <= y.n ; i++ ) {
		for ( j = 1 ; j <= y.m ; j++ ) {
			y.a[i][j] = -1;
		}
	}
	for ( i = 1 ; i <= x1.n ; i++ ) {
		for ( j = 1 ; j <= x1.m ; j++ ) {
			if ( x1.a[i][j] == -1 ) continue;
			for ( k = 1 ; k <= x2.m ; k++ ) {
				if ( 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;
}
void work () {
	int i , j , k , u , v , w;
	int s , t;
	//n = 50; m = 2500;
	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++ ) {
		/*u = (i-1) / n + 1;
		v = (i-1) % n + 1;
		w = rand () % 10000;*/
		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 );
	}
	ini[0].n = ini[0].m = ini100[0].n = ini100[0].m = n;
	for ( i = 1 ; i <=n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			ini[0].a[i][j] = ini100[0].a[i][j] = -1;
		}
		ini[0].a[i][i] = ini100[0].a[i][i] = 0;
	}
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 1 ; j <= n ; j++ ) {
			ini[1].a[i][j] = dis[i][j];
		}
	}
	ini[1].n = ini[1].m = n;
	for ( i = 2 ; i <= 100 ; i++ ) {
		ini[i] = ini[1] * ini[i-1];
	}
	ini100[1] = ini[100];
	for ( i = 2 ; i <= 100 ; i++ ) {
		ini100[i] = ini100[1] * ini100[i-1];
	}
	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] );
				}
			}
		}
	}
	//q = 100000;
	scanf ( "%d" , &q );
	for ( i = 1 ; i <= q ; i++ ) {
		/*s = rand () % n + 1;
		t = rand () % n + 1;
		k = rand () % 10000 + 1;*/
		scanf ( "%d%d%d" , &s , &t , &k );
		now.n = 1;
		now.m = n;
		for ( j = 1; j <= n ; j++ ) now.a[1][j] = ini[k%100].a[s][j];
		now = now * ini100[k/100];
		ans = -1;
		for ( j = 1 ; j <= n ; j++ ) {
			if ( now.a[1][j] != -1 && dis[j][t] != -1 ) {
				if ( ans == -1 ) ans = now.a[1][j] + dis[j][t];
				else ans = min ( ans , now.a[1][j] + dis[j][t] );
			}
		}
		printf ( "%d\n" , ans );
	}
}
int main () {
	int t;
	scanf ( "%d" , &t );
	while ( t-- ) {
		work ();
		clear ();
	}
	return 0;
}