// Not afraid to dark.

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

clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
    int llen;
    inline int get_string (char c[], int &len = llen){
        len = 0;
        read_char = getchar ();
        while (read_char == ' ' || read_char == '\n' || read_char == '\r')
            read_char = getchar ();
        while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
            c[++ len] = read_char;
            read_char = getchar ();
        }
        return len;
    }
}

const int N = 1e6, inf = 0x3f3f3f3f;
int n, m;
int firs[N + 5], nex[N * 2 + 5], to[N * 2 + 5], w[N * 2 + 5], tot = 1;
int deg[N + 5];
bool vis[N + 5];

vector < int > gL[N + 5], tL[N + 5];

inline void Add (int u, int v, int l){
    ++ deg[u], ++ deg[v];
    ++ tot;
    nex[tot] = firs[u];
    firs[u] = tot;
    to[tot] = v;
    w[tot] = l;
    ++ tot;
    nex[tot] = firs[v];
    firs[v] = tot;
    to[tot] = u;
    w[tot] = l;
}
inline void Add_L (int u, int v, int e){
    gL[v].push_back (e ^ 1);
    tL[u].push_back (e);
}

int Q;
pair < int , int > Query[N + 5];

unordered_map < int , int > QS[N + 5], QT[N + 5];
unordered_map < int , int > qS[N + 5], qT[N + 5];
unordered_map < int , int > TT;

signed main (){
    GET_START

    io::read (n), io::read (m);
    for (int i = 1, u, v, l;i <= m;++ i){
        io::read (u), io::read (v), io::read (l);
        Add (u, v, l);
    }
    queue < int > Que;
    for (int i = 1;i <= n;++ i)
        if (deg[i] <= 5)
            Que.push (i);
    while (! Que.empty ()){
        int u = Que.front ();
        Que.pop ();
        vis[u] = true;
        for (int e = firs[u], v;e;e = nex[e]){
            v = to[e];
            -- deg[v];
            if (! vis[v])
                Add_L (v, u, e ^ 1);
            if (deg[v] == 5)
                Que.push (v);
        }
    }
    io::read (Q);
    for (int i = 1, s, t;i <= Q;++ i){
        io::read (s), io::read (t);
        Query[i] = make_pair (s, t);
        QS[s][t] = inf, QT[t][s] = inf;
        // QS[s][t].push_back (i);// , qS[s][t].push_back (i);
        // QT[t][s].push_back (i);// , qT[t][s].push_back (i);
        // int ned = i;
        for (int e : gL[s]){
            int u = to[e];
            qS[u][t] = inf;
            qT[t][u] = inf;
        }
        for (int e : gL[t]){
            int v = to[e];
            qS[s][v] = inf;
            qT[v][s] = inf;
        }
    }
    for (int i = 1;i <= n;++ i){
        TT.clear ();
        int j, u, v, x, y, z;
        for (int ej : tL[i]){
            j = to[ej], x = w[ej];
            if (TT[j] == 0 || TT[j] > x)
                TT[j] = x;
            for (auto eu : gL[j]){
                u = to[eu], y = w[eu];
                if (TT[u] == 0 || TT[u] > x + y)
                    TT[u] = x + y;
            }
        }
        for (auto ej : gL[i]){
            j = to[ej], x = w[ej];
            if (TT[j] == 0 || TT[j] > x)
                TT[j] = x;
            for (auto eu : gL[j]){
                u = to[eu], y = w[eu];
                if (TT[u] == 0 || TT[u] > x + y)
                    TT[u] = x + y;
            }
        }
        TT[i] = 0;
        for (auto re : TT){
            tie (j, x) = re;
            qS[i][j] = min (qS[i][j], x);
        }
        for (int ej : tL[i]){
            j = to[ej], x = w[ej];
            for (int eu : gL[j]){
                u = to[eu], y = w[eu];
                for (int ev : gL[u]){
                    v = to[ev], z = w[ev];
                    if (TT[v] == 0 || TT[v] > x + y + z)
                        TT[v] = x + y + z;
                }
            }
        }
        TT[i] = 0;
        for (auto re : TT){
            tie (j, x) = re;
            QS[i][j] = min (QS[i][j], x);
        }

        TT.clear ();
        for (int ej : tL[i]){
            j = to[ej], x = w[ej];
            if (TT[j] == 0 || TT[j] > x)
                TT[j] = x;
            for (int eu : gL[j]){
                u = to[eu], y = w[eu];
                if (TT[u] == 0 || TT[u] > x + y)
                    TT[u] = x + y;
            }
        }
        for (int ej : gL[i]){
            j = to[ej], x = w[ej];
            if (TT[j] == 0 || TT[j] > x)
                TT[j] = x;
            for (int eu : gL[j]){
                u = to[eu], y = w[eu];
                if (TT[u] == 0 || TT[u] > x + y)
                    TT[u] = x + y;
            }
        }
        TT[i] = 0;
        for (auto re : TT){
            tie (j, x) = re;
            qT[i][j] = min (qT[i][j], x);
        }
        for (int ej : tL[i]){
            j = to[ej], x = w[ej];
            for (int eu : gL[j]){
                u = to[eu], y = w[eu];
                for (int ev : gL[u]){
                    v = to[ev], z = w[ev];
                    if (TT[v] == 0 || TT[v] > x + y + z)
                        TT[v] = x + y + z;
                }
            }
        }
        TT[i] = 0;
        for (auto re : TT){
            tie (j, x) = re;
            QT[i][j] = min (QT[i][j], x);
        }
    }
    for (int i = 1, s, t;i <= Q;++ i){
        tie (s, t) = Query[i];
        // int ned = i;
        int Ans = min (QS[s][t], QT[t][s]);
        for (int e : gL[s])
            Ans = min (Ans, min (qS[to[e]][t], qT[t][to[e]]) + w[e]);
        for (int e : gL[t])
            Ans = min (Ans, min (qS[s][to[e]], qT[to[e]][s]) + w[e]);
        if (Ans ^ inf)
            io::write (Ans), puts ("");
        else
            puts ("-1");
    }

    GET_END
    return 0;
}