#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <tuple> // For raw_edges
using namespace std;
// Define constants for array sizes and infinity
const long long INF = 1e18; // Use long long for distances
const int MAXN = 100005;
const int MAXM = 500005;
const int MAXQ = 100005;
// Maximum possible distance could be N * max_weight = 10^5 * 1000 = 10^8
// Define a safe upper bound for binary search range
const int MAX_DIST_THRESHOLD = 100000001; // Max possible threshold + 1
// Adjacency list to store the graph: pair<neighbor, weight>
vector<pair<int, int>> adj[MAXN];
// Array to store the minimum distance from each city to the nearest NPP
long long dist_npp[MAXN];
// Number of cities, roads, NPPs, and queries
int n, m, k, Q;
// --- Disjoint Set Union (DSU) ---
int parent[MAXN];
void init_dsu() {
iota(parent + 1, parent + n + 1, 1);
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void unite_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
parent[b] = a;
}
}
// --- End DSU ---
// Structure to represent edges along with their safety threshold
struct Edge {
int u, v;
int threshold; // min(dist_npp[u], dist_npp[v])
};
// Comparison function for sorting edges by threshold descending
bool compareEdges(const Edge& a, const Edge& b) {
return a.threshold > b.threshold;
}
// Structure to represent queries
struct Query {
int s, t, id;
};
// Arrays to store the binary search range [L, R) and final answer for each query
int L[MAXQ], R[MAXQ];
// Final answer will be stored in L[i] after iterations
// Vector to store queries grouped by their 'mid' value in each iteration
vector<pair<int, int>> mid_query_pairs; // Stores {mid, query_original_index}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// --- Read Graph ---
cin >> n >> m;
vector<tuple<int, int, int>> raw_edges; // Store edges temporarily
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
raw_edges.emplace_back(u, v, w);
}
// --- Read NPP locations and run Multi-Source Dijkstra ---
cin >> k;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
fill(dist_npp + 1, dist_npp + n + 1, INF);
for (int i = 0; i < k; ++i) {
int npp_city;
cin >> npp_city;
if (dist_npp[npp_city] > 0) { // Add only if not already 0
dist_npp[npp_city] = 0;
pq.push({0, npp_city});
}
}
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist_npp[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist_npp[u] + weight < dist_npp[v]) {
dist_npp[v] = dist_npp[u] + weight;
pq.push({dist_npp[v], v});
}
}
}
// --- Prepare Edges with Thresholds ---
vector<Edge> edges;
edges.reserve(m);
int max_possible_threshold = 0;
for(const auto& edge_tuple : raw_edges) {
int u, v, w;
tie(u, v, w) = edge_tuple;
long long threshold_ll = min(dist_npp[u], dist_npp[v]);
// Handle potential INF if a node is unreachable from any NPP (problem guarantees connectivity)
int threshold_int = (threshold_ll >= MAX_DIST_THRESHOLD) ? (MAX_DIST_THRESHOLD -1) : (int)threshold_ll;
if (threshold_ll == INF) continue; // Should not happen based on problem statement
edges.push_back({u, v, threshold_int});
max_possible_threshold = max(max_possible_threshold, threshold_int);
}
sort(edges.begin(), edges.end(), compareEdges); // Sort descending by threshold
// --- Read Queries and Initialize Binary Search ---
cin >> Q;
vector<Query> queries(Q);
for (int i = 0; i < Q; ++i) {
cin >> queries[i].s >> queries[i].t;
queries[i].id = i;
L[i] = 0;
R[i] = max_possible_threshold + 1; // Upper bound (exclusive)
}
// --- Parallel Binary Search (Corrected Logic) ---
for (int iter = 0; iter < 35; ++iter) { // ~log2(MaxDist) iterations
init_dsu();
mid_query_pairs.clear();
for (int i = 0; i < Q; ++i) {
if (L[i] != R[i]) {
int mid = L[i] + (R[i] - L[i]) / 2;
mid_query_pairs.push_back({mid, i});
}
}
if (mid_query_pairs.empty()) break;
sort(mid_query_pairs.rbegin(), mid_query_pairs.rend()); // Sort descending by mid
int edge_idx = 0;
for (const auto& mid_pair : mid_query_pairs) {
int mid = mid_pair.first;
int query_idx = mid_pair.second; // Original index of the query
Query& q = queries[query_idx]; // Get s, t from original query structure
// Add edges with threshold >= mid
while (edge_idx < edges.size() && edges[edge_idx].threshold >= mid) {
unite_sets(edges[edge_idx].u, edges[edge_idx].v);
edge_idx++;
}
// Check connectivity for this query
if (dist_npp[q.s] >= mid && dist_npp[q.t] >= mid && find_set(q.s) == find_set(q.t)) {
L[query_idx] = mid; // Possible, try [mid, R)
} else {
R[query_idx] = mid; // Not possible, try [L, mid)
}
}
} // End of binary search iterations
// --- Output Results ---
for (int i = 0; i < Q; ++i) {
cout << L[i] << "\n";
}
return 0;
}
