Hint
Calculate Floyd-Warshall once (O(n³) = 2.7·107), and then answer every query in O(1) from the matrix. A road is two-way – write the weight into d[u][v] and d[v][u].
Solution (C++)
#include <iostream>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
long long d[301][301];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) d[i][j] = (i == j) ? 0 : INF;
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
d[v][u] = min(d[v][u], w);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][k] != INF && d[k][j] != INF)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
cout << (d[a][b] == INF ? -1 : d[a][b]) << "\n";
}
return 0;
}