#include<bits/stdc++.h>
using namespace std;

const int N = 510, M = 3010;
int n, m, q;
struct Edge
{
	int a, b, w;
};
vector<Edge> edge, tree;

int h[N], ne[M], e[M], w[M], idx;
void add(int a, int b, int c)
{
	e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

int dis[N], cnt[N], s, t;
int sap(int x, int inflow)
{
	if(x == t) return inflow;
	int outflow = 0;
	for(int i = h[x]; i; i = ne[i])
		if(w[i] && dis[x] == dis[e[i]] + 1)
		{
			int flow = sap(e[i], min(inflow - outflow, w[i]));
			w[i] -= flow, w[i ^ 1] += flow, outflow += flow;
			if(inflow == outflow || dis[s] >= n + 1) return outflow; 
		}
	if(!--cnt[dis[x]]) dis[s] = n + 1;
	cnt[++dis[x]]++;
	return outflow;
}

int id[N];
bool flag[N], vis[N]; 
void solve(int l, int r)
{
	if(l == r) return;
	
	memset(h, 0, sizeof(h)), idx = 1;
	memset(dis, 0, sizeof(dis));
	memset(cnt, 0, sizeof(cnt));
	memset(flag, 0, sizeof(flag));
	memset(vis, 0, sizeof(vis));
	for(int i = l; i <= r; i++) flag[id[i]] = 1;
	for(Edge i : edge)
		if(!flag[i.a] && !flag[i.b]) add(i.a, i.b, 1e9), add(i.b, i.a, 1e9);
		else add(i.a, i.b, i.w), add(i.b, i.a, i.w);
	s = id[l], t = id[r];
	
	int res = 0;
	while(dis[s] <= n) res += sap(s, 1e9);
	tree.push_back({s, t, res});
	
	queue<int> q;
	vis[s] = 1, q.push(s);
	while(!q.empty())
	{
		int t = q.front(); q.pop();
		for(int i = h[t]; i; i = ne[i])
			if(w[i] && !vis[e[i]]) vis[e[i]] = 1, q.push(e[i]);
	}
	
	vector<int> s1, s2;
	for(int i = l; i <= r; i++)
		if(vis[id[i]]) s1.push_back(id[i]);
		else s2.push_back(id[i]);
	for(int i = 0; i < s1.size(); i++) id[l + i] = s1[i];
	for(int i = 0; i < s2.size(); i++) id[l + s1.size() + i] = s2[i];
	
	solve(l, l + s1.size() - 1), solve(r - s2.size() + 1, r);
}

int main()
{
	cin >> n >> m;
	for(int i = 1, a, b, c; i <= m; i++)
		scanf("%d%d%d", &a, &b, &c), edge.push_back({a, b, c});
	for(int i = 1; i <= n; i++) id[i] = i;
	solve(1, n);
	memset(h, 0, sizeof(h)), idx = 0;
	for(Edge i : tree) add(i.a, i.b, i.w), add(i.b, i.a, i.w);
	
	cin >> q;
	while(q--)
	{
		memset(dis, 0x3f, sizeof(dis));
		int a, b;
		scanf("%d%d", &a, &b);
		queue<int> q;
		dis[a] = 1e8, q.push(a);
		while(!q.empty())
		{
			int t = q.front(); q.pop();
			if(t == b)
			{
				printf("%d\n", dis[t]);
				break;
			}
			
			for(int i = h[t]; i; i = ne[i])
				if(dis[e[i]] > 1e9) dis[e[i]] = min(dis[t], w[i]), q.push(e[i]);
		}
	}
	return 0;
}