/**
* Author: Tran Dang Khoa
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,l,r) for (int i = (l), _r = (r); i <= _r; i++)
#define REP(i,l,r) for (int i = (l), _r = (r); i < _r; i++)
#define FORN(i,r,l) for (int i = (r), _l = (l); i >= _l; i--)
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define sz(x) (int)x.size()
#define all(v) (v).begin(),(v).end()
#define allVector(v, n) (v).begin() + 1, (v).begin() + (n) + 1
#define segleft (id << 1)
#define segright (id << 1 | 1)
#define tcT template <class T
tcT> bool minimize(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
tcT> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
const int MOD = 1e9+7;
void iofile(string s) {
freopen((s + ".inp").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct infoQuery {
int a, b;
infoQuery(int _a = 0, int _b = 0) {
a = _a;
b = _b;
}
};
const ll INF = 1e9;
const int N = 1e5 + 1;
vector<pair<int,ll>> edge[N];
vector<int> npp;
vector<ll> dist;
vector<infoQuery> query;
int n, m, k, q;
int checksub() {
bool flag = true;
for (int i = 1, a, b; i <= q; i++) {
a = query[i].a, b = query[i].b;
auto it = lb(all(edge[a]), make_pair(b, -1LL));
if (it -> first != b) {
flag = false;
break;
}
}
if (n <= 1000 && m <= 1000 && q <= 1000 && flag) {
return 1;
} else if (n <= 100000 && q <= 100000 && flag) {
return 2;
} else if (n <= 15 && m <= 200 && q <= 200) {
return 3;
} else if (q == 1) {
return 4;
}
return 5;
}
struct DisjointSet {
vector<int> num, par;
int n;
DisjointSet(int _n) {
n = _n;
num.assign(n + 1, 0);
par.assign(n + 1, 0);
iota(all(par), 0);
fill(all(num), 1);
}
void init() {
iota(all(par), 0);
fill(all(num), 1);
}
int findpar(int u) {
return (par[u] == u ? u : par[u] = findpar(par[u]));
}
bool unite(int u, int v) {
u = findpar(u);
v = findpar(v);
if (u == v) return false;
if (num[u] < num[v]) swap(u, v);
par[v] = u;
num[u] += num[v];
return true;
}
};
void Dijkstra_Root(int st) {
dist.assign(n + 1, INF);
dist[st] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
q.push({0, st});
while (!q.empty()) {
auto[du, u] = q.top(); q.pop();
if (du > dist[u]) continue;
for (auto[v, w] : edge[u]) {
if (minimize(dist[v], dist[u] + w)) {
q.push({dist[v], v});
}
}
}
}
void Dijkstra_Multicore() {
dist.assign(n + 1, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
for (int u : npp) {
dist[u] = 0;
q.push({0, u});
}
while (!q.empty()) {
auto[du, u] = q.top(); q.pop();
if (du > dist[u]) continue;
for (auto[v, w] : edge[u]) {
if (minimize(dist[v], dist[u] + w)) {
q.push({dist[v], v});
}
}
}
}
namespace subtask1 {
void solve() {
for (int i = 1, a, b; i <= q; i++) {
a = query[i].a, b = query[i].b;
ll ans = INF;
Dijkstra_Root(a);
for (int u : npp) minimize(ans, dist[u]);
Dijkstra_Root(b);
for (int u : npp) minimize(ans, dist[u]);
cout << ans << endl;
}
}
}
namespace subtask2 {
void solve() {
Dijkstra_Multicore();
for (int i = 1, a, b; i <= q; i++) {
a = query[i].a, b = query[i].b;
cout << min(dist[a], dist[b]) << endl;
}
}
}
namespace subtask3 {
ll ans = -INF;
struct info {
int u;
ll used, path_result;
};
void bfs(int st, int ed) {
deque<info> q;
q.pb({st, MASK(st), dist[st]});
while (!q.empty()) {
info cur = q.front(); q.pop_front();
if (cur.u == ed) {
maximize(ans, cur.path_result);
continue;
}
for (auto[v, w] : edge[cur.u]) {
if (BIT(cur.used, v)) continue;
q.pb({v, cur.used | MASK(v), min(cur.path_result, dist[v])});
}
}
}
void solve() {
Dijkstra_Multicore();
for (int i = 1, a, b; i <= q; i++) {
a = query[i].a, b = query[i].b;
ans = -INF;
bfs(a, b);
cout << ans << endl;
}
}
}
namespace subtask4 {
bool check(ll x) {
DisjointSet dsu(n);
FOR(u, 1, n) {
if (dist[u] < x) continue;
for (auto[v, w] : edge[u]) {
if (dist[v] >= x) {
dsu.unite(u, v);
}
}
}
return dsu.findpar(query[1].a) == dsu.findpar(query[1].b);
}
void solve() {
Dijkstra_Multicore();
ll l = 0, r = INF;
ll ans;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << endl;
}
}
namespace subtask5 {
struct infoMid {
ll mid;
int u, v, id;
};
vector<infoMid> canMid;
void solve() {
Dijkstra_Multicore();
vector<ll> l(q + 1, 0), r(q + 1, INF), ans(q + 1);
vector<int> order(n + 1);
iota(all(order), 0);
sort(allVector(order, n), [](int &a, int &b) {
return dist[a] > dist[b];
});
DisjointSet dsu(n);
bool flag = true;
while (flag) {
flag = false;
FOR(i, 1, q) {
if (l[i] > r[i]) continue;
flag = true;
ll mid = (l[i] + r[i]) >> 1;
canMid.pb({mid, query[i].a, query[i].b, i});
}
if (!flag) break;
sort(all(canMid), [](infoMid &a, infoMid &b) {
return a.mid > b.mid;
});
int index = 0;
FOR(i, 1, n) {
int u = order[i];
for (auto[v, w] : edge[u]) if (dist[v] >= dist[u]) dsu.unite(u, v);
while (index < sz(canMid) && canMid[index].mid > dist[u]) {
int id = canMid[index].id;
r[id] = canMid[index].mid - 1;
index++;
}
ll nxt = (i < n ? dist[order[i + 1]] : -1);
while (index < sz(canMid) && canMid[index].mid > nxt) {
int id = canMid[index].id;
if (dsu.findpar(canMid[index].u) == dsu.findpar(canMid[index].v)) {
ans[id] = canMid[index].mid;
l[id] = canMid[index].mid + 1;
} else {
r[id] = canMid[index].mid - 1;
}
index++;
}
}
vector<infoMid>().swap(canMid);
dsu.init();
}
FOR(i, 1, q) cout << ans[i] << endl;
}
}
void input() {
cin >> n >> m;
for (ll i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
edge[u].pb({v, w});
edge[v].pb({u, w});
}
// sort edge to lb in checksub
FOR(i, 1, n) sort(all(edge[i]));
cin >> k;
for (int i = 1, u; i <= k; i++) {
cin >> u;
npp.pb(u);
}
cin >> q;
query.assign(q + 1, infoQuery());
for (int i = 1, a, b; i <= q; i++) {
cin >> a >> b;
query[i] = {a, b};
}
}
void trandkhoa() {
input();
// int subtask = checksub();
subtask3::solve();
/*
switch (subtask) {
case 1:
subtask1::solve();
break;
case 2:
subtask2::solve();
break;
case 3:
subtask3::solve();
break;
case 4:
subtask4::solve();
break;
default:
subtask5::solve();
}
*/
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
//iofile("");
int test = 1;
//cin >> test;
while(test--) trandkhoa();
return (0 ^ 0);
}
