#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=1e6+10;
const double max_load_cap=1;

int inf=1e9;

struct chash{
    const uint64_t C= (ll)(4e18*acos(0))|71;
    ll operator()(ll x)const{return __builtin_bswap64(x*C);}
};

vector<pii>vg[maxn],vout[maxn],vin[maxn];
vector<int>niz,revniz;
unordered_map<int,int,chash>map_out[maxn],map_in[maxn],map_rez[maxn];

int n,m,deg[maxn],pos[maxn],q,rez_qry[maxn];

void init(){

    for(int i=1;i<=n;i++){
        map_out[i].max_load_factor(max_load_cap);
        map_in[i].max_load_factor(max_load_cap);
        map_rez[i].max_load_factor(max_load_cap);

        for(int j=0;j<vout[i].size();j++)map_out[i][vout[i][j].ff]=vout[i][j].ss;
        for(int j=0;j<vin[i].size();j++)map_in[i][vin[i][j].ff]=vin[i][j].ss;

        ///printf("%d %d AAA\n",i,niz[i]);
    }

}

void prek(){

    vector<int>good;
    for(int i=1;i<=n;i++){
        if(deg[i]<=5)good.pb(i);
    }

    niz.pb(0);
    revniz.resize(n+1);
    for(int i=1;i<=n;i++){
        int id=good.back();
        good.pop_back();
        niz.pb(id);
        revniz[id]=niz.size()-1;
        pos[id]=1;

        for(int j=0;j<vg[id].size();j++){
            int id2=vg[id][j].ff;
            if(pos[id2])continue;
            deg[id2]--;
            if(deg[id2]==5)good.pb(id2);
        }

        ///printf("%d %d MAP\n",i,id);
    }

    for(int i=1;i<=n;i++){

        for(int j=0;j<vg[i].size();j++){
            int id=vg[i][j].ff;
            int w=vg[i][j].ss;

            int a=revniz[i];
            int b=revniz[id];

            if(a>b){
                continue;
            }

            vout[a].pb({b,w});
            vin[b].pb({a,w});
        }

    }

}

void update_rez(int a,int b,int w){
    if(a>b)swap(a,b);
    if(map_rez[a].find(b)==map_rez[a].end())map_rez[a][b]=w;
    else{
        int &p=map_rez[a][b];
        p=min(p,w);
    }
}

void go_LR(){

    for(int i=1;i<=n;i++){

        for(int j=0;j<vout[i].size();j++){
            int id1=vout[i][j].ff;
            int w1=vout[i][j].ss;

            update_rez(i,id1,w1);

            for(int k=j+1;k<vout[i].size();k++){
                int id2=vout[i][k].ff;
                int w2=vout[i][k].ss;

                update_rez(id1,id2,w1+w2);
            }
        }

    }

}
void go_lrr_llr(){

    for(int i=1;i<=n;i++){

        for(int j=0;j<vout[i].size();j++){
            int id1=vout[i][j].ff;
            int w1=vout[i][j].ss;

            for(int k=0;k<vout[i].size();k++){
                int id2=vout[i][k].ff;
                if(id2==id1)continue;
                int w2=vout[i][k].ss;

                for(int p=0;p<vout[id2].size();p++){
                    int id3=vout[id2][p].ff;
                    int w3=vout[id2][p].ss;

                    ///printf("%d %d %d %d AAA\n",i,id1,id2,id3);

                    update_rez(id1,id3,w1+w2+w3);
                }

            }
        }

    }

}

struct qry{
    int a,b,w,id;
}pocqry[maxn];

vector<qry>newqry;

void go_make_k2(){

    for(int i=1;i<=q;i++){

        int a=pocqry[i].a;
        int b=pocqry[i].b;

        qry pom2;
        pom2.id=i;
        pom2.a=a;
        pom2.b=b;
        pom2.w=0;
        newqry.pb(pom2);

        for(int j=0;j<vout[a].size();j++){
            int id=vout[a][j].ff;
            int w=vout[a][j].ss;

            qry pom;
            pom.id=pocqry[i].id;
            pom.w=w;
            pom.a=id;
            pom.b=b;
            ///printf("%d %d EDGE A\n",pom.a,pom.b);
            if(pom.a>pom.b)swap(pom.a,pom.b);
            newqry.pb(pom);
        }
        for(int j=0;j<vout[b].size();j++){
            int id=vout[b][j].ff;
            int w=vout[b][j].ss;

            qry pom;
            pom.id=pocqry[i].id;
            pom.w=w;
            pom.a=a;
            pom.b=id;
            ///printf("%d %d EDGE B\n",pom.a,pom.b);
            if(pom.a>pom.b)swap(pom.a,pom.b);
            newqry.pb(pom);
        }
    }

    /*for(int i=0;i<newqry.size();i++){
        printf("%d %d %d %d NQ\n",newqry[i].a,newqry[i].b,newqry[i].id,newqry[i].w);
    }*/

}
void go_upd_LR_k2(){
    return;
    for(int i=0;i<newqry.size();i++){
        if(map_rez[newqry[i].a].find(newqry[i].b)!=map_rez[newqry[i].a].end())
            rez_qry[newqry[i].id]=min(rez_qry[newqry[i].id],map_rez[newqry[i].a][newqry[i].b]+newqry[i].w);
    }
}

void go_RR_k2(){

    for(int i=1;i<=n;i++){

        for(int j=0;j<vin[i].size();j++){
            for(int k=0;k<vout[i].size();k++){
                int id1=vin[i][j].ff;
                int id2=vout[i][k].ff;
                int w1=vin[i][j].ss;
                int w2=vout[i][k].ss;

                ///printf("%d %d |");
                update_rez(id1,id2,w1+w2);
            }
        }

    }

    for(int i=0;i<newqry.size();i++){
        if(map_rez[newqry[i].a].find(newqry[i].b)!=map_rez[newqry[i].a].end()){
            rez_qry[newqry[i].id]=min(rez_qry[newqry[i].id],map_rez[newqry[i].a][newqry[i].b]+newqry[i].w);
            ///printf("%d %d | %d %d ADDED\n",newqry[i].a,newqry[i].b,newqry[i].w,map_rez[newqry[i].a][newqry[i].b]);
        }
    }

}

void go_RL_k2(){

    for(int i=0;i<newqry.size();i++){
        int id=newqry[i].id;
        int a=newqry[i].a;
        int b=newqry[i].b;
        int w=newqry[i].w;

        for(int j=0;j<vout[a].size();j++){
            int id2=vout[a][j].ff;
            int w2=vout[a][j].ss;

            if(map_in[id2].find(b)!=map_in[id2].end())
                rez_qry[id]=min(rez_qry[id],w2+w+map_in[id2][b]);
        }

    }

}

void dfs(int x,int h,int goal,int cw,int &ret){

    if(goal==x){
        ret=min(ret,cw);
        return;
    }
    if(h==0)return;

    for(int i=0;i<vg[x].size();i++){
        int id=vg[x][i].ff;
        dfs(id,h-1,goal,cw+vg[x][i].ss,ret);
    }
}
int get_qry(int a,int b){
    int ret=inf;
    dfs(a,3,b,0,ret);
    if(ret==inf)return -1;
    return ret;
}
int rpqa[maxn],rpqb[maxn];
int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        vg[a].pb({b,w});
        vg[b].pb({a,w});
        deg[a]++;
        deg[b]++;
    }

    prek();
    init();


    go_LR();

    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        rez_qry[i]=inf;
        int a,b;
        scanf("%d %d",&a,&b);
        rpqa[i]=a;
        rpqb[i]=b;
        a=revniz[a];
        b=revniz[b];
        if(a>b)swap(a,b);
        pocqry[i].id=i;
        pocqry[i].a=a;
        pocqry[i].b=b;
        pocqry[i].w=0;
    }
    go_make_k2();

    go_upd_LR_k2();
    go_RR_k2();
    go_RL_k2();
    go_lrr_llr();

    for(int i=1;i<=q;i++){
        int a=pocqry[i].a;
        int b=pocqry[i].b;
        if(map_rez[a].find(b)!=map_rez[a].end())rez_qry[i]=min(rez_qry[i],map_rez[a][b]);
        if(rez_qry[i]==inf)rez_qry[i]=-1;
        printf("%d\n",rez_qry[i]);
        //printf("%d REAL\n",get_qry(rpqa[i],rpqb[i]));

        /*if(rez_qry[i]!=get_qry(rpqa[i],rpqb[i])){
            printf("%d %d %d\n",i,rez_qry[i],get_qry(rpqa[i],rpqb[i]));
        }*/
    }

    return 0;
}