打了一个最大生成树+dfs，60分成功tle
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
const int maxm = 50005;
int n, m, cnt = 0;
struct edge
{
int from, to, value;
bool operator < (const edge b) const {
return this->value > b.value;
}
}es[maxm];
vector<edge> G[maxn];
struct car
{
int from, to;
}cs[30001];
int q;
void read() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
es[cnt].from = x;
es[cnt].to = y;
es[cnt].value = z;
cnt++;
}
cin >> q;
for(int i = 1; i <= q; i++) cin >> cs[i].from >> cs[i].to;
}
int fa[maxn];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void kruskal() {
sort(es, es+cnt);
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 0; i < cnt; i++) {
int x = es[i].from; int y = es[i].to;
int fx = find(x); int fy = find(y);
if(fx == fy) {
es[i].value = -1;
continue;
}
else fa[fx] = fy;
}
}
void build_tree() {
sort(es, es+cnt);
for(int i = 0; i < cnt; i++) {
if(es[i].value != -1) {
int x = es[i].from;
int y = es[i].to;
G[x].push_back({x, y, es[i].value});
G[y].push_back({y, x, es[i].value});
}
else break;
}
}
int mini = 0x3f3f3f;
int vis[maxn];
void dfs(int from, int to, int m) {
vis[from] = 1;
if(from == to) {mini = m; return;}
vector<edge>::iterator it;
for(it = G[from].begin(); it != G[from].end(); it++) {
edge &e = *it;
if(!vis[e.to]) {
dfs(e.to, to, min(m, e.value));
}
}
}
void solve() {
for(int i = 1; i <= q; i++) {
int x = cs[i].from;
int y = cs[i].to;
mini = 0x3f3f3f;
memset(vis, 0, sizeof(vis));
dfs(x, y, 0x3f3f3f);
if(mini == 0x3f3f3f) cout << -1;
else cout << mini;
cout << endl;
}
}
int main() {
// freopen("input.in", "r", stdin);
read();
kruskal();
build_tree();
solve();
return 0;
}