算法：最小生成树，树上倍增。
这道题要先知道一个结论，那就是货车走过的道路一定是在最大生成树上面的，证明可以使用反证法。十分显然。
之后，我们得到一棵树之后，就可以树上倍增了。我们同时维护一个lca数组和一个ans数组，分别用来表示从它开始第(2^k)父亲的节点和到父亲节点这么多地方最小的边权。到时候取答案就和lca一样。注意特判不在一棵树上的时候，直接使用最小生成树的时候使用的并查集就好了。
这个题目告诉我们，一些图论问题，把它转换为树之后，之后树上倍增就做到(nlogn)的时间复杂度，可以过很多题目。
直接上代码。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<ctime>
using namespace std;
#define TMP template < class ins >
#define endl '
'
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;t++)
#define ERP(t,a) for(register int t=head[(a)];t;t=e[t].nx)
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;t--)
typedef long long ll;
TMP inline ins qr(ins tag){
char c=getchar();
ins x=0;
int q=0;
while(c<48||c>57)
q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)
x=x*10+c-48,c=getchar();
return q==-1?-x:x;
}
const int maxe=50005;
const int maxn=10005;
struct E{
int to,w,nx;
}e[maxe<<1];
struct pre{
int fr,to,w;
inline bool operator < (pre y){
return w>y.w;
}
}data[maxe];
int head[maxn];
int cnt;
int Q;
inline void add(int fr,int to,int w,bool boooooo){
e[++cnt]=(E){to,w,head[fr]};
head[fr]=cnt;
if(boooooo)
add(to,fr,w,0);
}
int r[maxn];
inline int f(int x){
int t=x;
while(r[t]!=t)
t=r[t];
int i=x,temp;
while(r[i]!=i){
temp=r[i];
r[i]=t;
i=temp;
}
return t;
}
int m,n;
inline void j(int x,int y){
r[f(x)]=f(y);
}
inline void mst(){
sort(data+1,data+m+1);
RP(t,1,n)
r[t]=t;
RP(t,1,m){
if(f(data[t].to)!=f(data[t].fr)){
j(data[t].to,data[t].fr);
add(data[t].to,data[t].fr,data[t].w,1);
// cout<<data[t].to<<' '<<data[t].fr<<' '<<data[t].w<<endl;
}
}
}
int d[maxn];
int l[maxn][19];
int ans[maxn][19];
int lg[maxn];
bool usd[maxn];
TMP inline ins minn(ins a,ins b,ins c){
if(a>b)
a=b;
if(a>c)
return c;
return a;
}
const int inf=99999999;
void dfs(int now,int last,int w){
d[now]=d[last]+1;
l[now][0]=last;
ans[now][0]=w;
RP(t,1,lg[d[now]]){
l[now][t]=l[l[now][t-1]][t-1];
ans[now][t]=min(ans[now][t-1],ans[l[now][t-1]][t-1]);
}
ERP(t,now)
if(e[t].to!=last)
dfs(e[t].to,now,e[t].w);
}
inline int ask(int x1,int x2){
if(f(x1)!=f(x2))
return -1;
if(d[x1]<d[x2])
swap(x1,x2);
int ret=inf;
while(d[x1]>d[x2])
ret=min(ans[x1][lg[d[x1]-d[x2]]],ret),x1=l[x1][lg[d[x1]-d[x2]]];
if(x1==x2)
return ret;
DRP(t,lg[d[x1]],0)
if(l[x1][t]!=l[x2][t])
ret=minn(ret,ans[x1][t],ans[x2][t]),x1=l[x1][t],x2=l[x2][t];
return minn(ret,ans[x1][0],ans[x2][0]);
}
int t1,t2;
inline void eff(){
RP(t,1,n){
lg[t]=lg[t-1];
if((1<<(lg[t]+1))==t)
lg[t]++;
}
RP(t,1,n)
if(!usd[f(t)])
usd[f(t)]=1,dfs(t,0,inf);
/*RP(t,1,n){
RP(i,0,lg[t])
cout<<ans[t][i]<<' ';
cout<<endl;
}
*/
Q=qr(1);
RP(t,1,Q){
t1=qr(1);
t2=qr(1);
cout<<ask(t1,t2)<<endl;
}
}
inline void init(){
n=qr(1);
m=qr(1);
RP(t,1,m){
data[t].fr=qr(1);
data[t].to=qr(1);
data[t].w=qr(1);
}
mst();
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
memset(ans,0x7f,sizeof ans);
return init(),eff(),0;
}