#include<bits/stdc++.h>
using namespace std;
int n,m;
struct qq{
    int a[52][52];
}L[110],R[210],I,E;
qq operator * (const qq &a,const qq &b){
    qq c;memset(c.a,0x3f,sizeof(c.a));
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
    c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
    return c;
}
qq operator + (const qq &a,const qq &b){
    qq c;memset(c.a,0x3f,sizeof(c.a));
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
    c.a[i][j]=min(a.a[i][j],b.a[i][j]);
    return c;
}
const int Q=1e9;
void sol(){
    scanf("%d%d",&n,&m);
    memset(E.a,0x3f,sizeof(E.a));
    memset(I.a,0x3f,sizeof(I.a));
    for(int i=1;i<=n;i++)I.a[i][i]=0;
    for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),E.a[u][v]=min(E.a[u][v],w);
    L[0]=R[0]=I;
    for(int i=1;i<=200;i++)R[i]=R[i-1]*E;
    for(int i=1;i<=100;i++)L[i]=L[i-1]*R[100];
    for(int i=200;i;i--)R[i-1]=R[i-1]+R[i];
    int q;scanf("%d",&q);while(q--){
        int u,v,k;scanf("%d%d%d",&u,&v,&k);
        int ans=Q;
        for(int i=1;i<=n;i++)
        ans=min(ans,L[k/100].a[u][i]+R[k%100].a[i][v]);
        if(ans==Q)puts("-1");
        else printf("%d\n",ans);
    }
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}