#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define fors(i, a, b) for(int i = a; i >= b; i--)
#define forr(i, a, b) for(int i = a; i < b; i++)
#define sim template <class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair<b, c> d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for(auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using Matrix = vector<vector<ll>>;
using cube = vector<vector<vector<ll>>>;
//-------Debug code-------
template <typename Func>
void TestPerformance(Func function) {
auto start = chrono::high_resolution_clock::now();
function();
auto end = chrono::high_resolution_clock::now();
auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
auto sec = chrono::duration<double>(end - start).count();
cout << "Elapsed time: " << ms << " ms (" << sec << " s)\n";
}
struct node {
ll idx, cost;
bool operator < (const node & other) const {
return cost > other.cost;
}
};
struct edge {
ll u, v, w;
bool operator < (const edge & other) const {
return w > other.w;
}
};
const ll INF = 1E18;
ll n, m, k, q, root = 1, LOG = 0;
vector<edge> e;
Matrix up, MIND;
vector<ll> depth;
vector<ll> g, dist;
vector<ll> parent, sz;
vector<vector<pair<ll, ll>>> adj, tree;
namespace DSU {
void makeset() {
for(ll i = 1; i <= n; i++) {
parent[i] = i;
sz[i] = 1;
}
}
ll trace(const ll & u) {
return (u == parent[u] ? u : parent[u] = trace(parent[u]));
}
bool uni(ll a, ll b) {
a = trace(a);
b = trace(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
}
namespace LCA {
void takeLOG() { while((1 << LOG) <= n) LOG++; }
void DFS(const ll & u, const ll & par, const ll & w) {
up[u][0] = par;
MIND[u][0] = w;
for(ll j = 1; j < LOG; j++) {
up[u][j] = up[up[u][j - 1]][j - 1];
MIND[u][j] = min(MIND[u][j - 1], MIND[up[u][j - 1]][j - 1]);
}
for(const auto & p : tree[u]) {
ll v = p.first, w = p.second;
if(v != par) {
depth[v] = depth[u] + 1;
DFS(v, u, w);
}
}
}
ll getanswer(ll u, ll v) {
ll answer = INF;
if(depth[u] < depth[v]) swap(u, v);
ll diff = depth[u] - depth[v];
for(ll j = 0; j < LOG; j++) {
if(diff & (1 << j)) {
answer = min(answer, MIND[u][j]);
u = up[u][j];
}
}
if(u == v) return min(answer, dist[u]);
for(ll j = LOG - 1; j >= 0; j--) {
if(up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
answer = min({answer, MIND[u][j], MIND[v][j]});
}
}
return min({answer, MIND[u][0], MIND[v][0]});
}
}
void Dijkstra() {
dist.assign(n + 1, INF);
priority_queue<node> pq;
for(ll i = 0; i < k; i++) {
dist[g[i]] = 0;
pq.push({g[i], 0});
}
while(!pq.empty()) {
node temp = pq.top(); pq.pop();
ll u = temp.idx, d = temp.cost;
if(d > dist[u]) continue;
for(const auto & p : adj[u]) {
ll v = p.first, w = p.second;
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({v, dist[v]});
}
}
}
}
void solve() {
cin >> n >> m;
adj.resize(n + 1);
for(ll i = 0; i < m; i++) {
ll u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
e.push_back({u, v, w});
}
cin >> k;
g.resize(k);
for(ll i = 0; i < k; i++) {
cin >> g[i];
}
Dijkstra();
/*for(ll i = 1; i <= n; i++) {
cout << dist[i] << " ";
}*/
//sử dụng đường đi ngắn nhất của 1 thành phố đến k gần nhất làm cạnh
//ta bắt đầu với tuyến đường u - v trực tiếp trước
for(ll i = 0; i < m; i++) {
e[i].w = min(dist[e[i].u], dist[e[i].v]);
}
sort(e.begin(), e.end());
parent.resize(n + 1);
sz.assign(n + 1, 0);
DSU::makeset();
tree.resize(n + 1);
//ta cần độ nguy hiểm càng lớn càng tốt -> tạo cây khung cực đại
//sử dụng dsu để kiểm tra chu trình
for(ll i = 0; i < m; i++) {
if(DSU::uni(e[i].u, e[i].v)) {
tree[e[i].u].push_back({e[i].v, e[i].w});
tree[e[i].v].push_back({e[i].u, e[i].w});
}
}
/*for(ll i = 1; i <= n; i++) {
if(!tree[i].empty()) {
for(const auto & p : tree[i]) {
cout << i << " " << p.first << " " << p.second << "\n";
}
}
}*/
//ví dụ với test đề thì MaxST là:
/*
1 9 8
1 2 3
2 4 0
3 6 5
5 9 8
5 8 7
6 8 5
7 8 0
*/
LCA::takeLOG();
up.resize(n + 1, vector<ll>(LOG));
MIND.assign(n + 1, vector<ll>(LOG, INF));
depth.resize(n + 1);
depth[root] = 0;
LCA::DFS(root, root, INF);
cin >> q;
while(q--) {
ll s, t; cin >> s >> t;
ll answer = LCA::getanswer(s, t);
answer = min({answer, dist[s], dist[t]});
cout << answer << "\n";
}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
/*cout << "[Do you want to test the performance?] (Yes / No) \n" << flush;
string ans; cin >> ans;
transform(ans.begin(), ans.end(), ans.begin(), ::tolower);
if(ans == "yes") TestPerformance(solve);
else solve();*/
solve();
return 0;
}
