#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> arr[100001],cst[100001];
int vis[100001];
struct node{
ll ind,val;
};
set<node> S;
bool operator < (node a,node b){
if(a.val!=b.val)return a.val<b.val;
return a.ind<b.ind;
}
ll solve(ll x,ll y){
S.insert({x,0});
while(S.size()){
node cur=*S.begin();
S.erase(S.begin());
if(vis[cur.ind]!=-1)continue;
vis[cur.ind]=cur.val;
if(cur.ind==y)break;
for(int i=0;i<arr[cur.ind].size();i++)
S.insert({arr[cur.ind][i],cst[cur.ind][i]+cur.val});
}
return vis[y];
}
int main() {
int cases;cin>>cases;
while(cases--){
ll n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
ll x,y,z;
cin>>x>>y>>z;
arr[x].push_back(y);
cst[x].push_back(z);
arr[y].push_back(x);
cst[y].push_back(z);
}
ll q;
cin>>q;
while(q--){
ll x,y;
cin>>x>>y;
memset(vis,-1,sizeof vis);
cout<<solve(x,y)<<endl;
for(int i=0;i<n;i++){
arr[i].clear();
cst[i].clear();
}
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvcjxsbD4gYXJyWzEwMDAwMV0sY3N0WzEwMDAwMV07CmludCB2aXNbMTAwMDAxXTsKc3RydWN0IG5vZGV7CglsbCBpbmQsdmFsOwp9OwpzZXQ8bm9kZT4gUzsKYm9vbCBvcGVyYXRvciA8IChub2RlIGEsbm9kZSBiKXsKCWlmKGEudmFsIT1iLnZhbClyZXR1cm4gYS52YWw8Yi52YWw7CglyZXR1cm4gYS5pbmQ8Yi5pbmQ7Cn0KbGwgc29sdmUobGwgeCxsbCB5KXsKCVMuaW5zZXJ0KHt4LDB9KTsKCXdoaWxlKFMuc2l6ZSgpKXsKCQlub2RlIGN1cj0qUy5iZWdpbigpOwoJCVMuZXJhc2UoUy5iZWdpbigpKTsKCQlpZih2aXNbY3VyLmluZF0hPS0xKWNvbnRpbnVlOwoJCXZpc1tjdXIuaW5kXT1jdXIudmFsOwoJCWlmKGN1ci5pbmQ9PXkpYnJlYWs7CgkJZm9yKGludCBpPTA7aTxhcnJbY3VyLmluZF0uc2l6ZSgpO2krKykKCQkJUy5pbnNlcnQoe2FycltjdXIuaW5kXVtpXSxjc3RbY3VyLmluZF1baV0rY3VyLnZhbH0pOwoJfQoJcmV0dXJuIHZpc1t5XTsKfQppbnQgbWFpbigpIHsKCWludCBjYXNlcztjaW4+PmNhc2VzOwoJd2hpbGUoY2FzZXMtLSl7CgkJbGwgbixtOwoJCWNpbj4+bj4+bTsKCQlmb3IoaW50IGk9MDtpPG07aSsrKXsKCQkJbGwgeCx5LHo7CgkJCWNpbj4+eD4+eT4+ejsKCQkJYXJyW3hdLnB1c2hfYmFjayh5KTsKCQkJY3N0W3hdLnB1c2hfYmFjayh6KTsKCQkJYXJyW3ldLnB1c2hfYmFjayh4KTsKCQkJY3N0W3ldLnB1c2hfYmFjayh6KTsKCQl9CgkJbGwgcTsKCQljaW4+PnE7CgkJd2hpbGUocS0tKXsKCQkJbGwgeCx5OwoJCQljaW4+Png+Pnk7CgkJCW1lbXNldCh2aXMsLTEsc2l6ZW9mIHZpcyk7CgkJCWNvdXQ8PHNvbHZlKHgseSk8PGVuZGw7CgkJCWZvcihpbnQgaT0wO2k8bjtpKyspewoJCQkJYXJyW2ldLmNsZWFyKCk7CgkJCQljc3RbaV0uY2xlYXIoKTsKCQkJfQoJCX0KCX0KCXJldHVybiAwOwp9