#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <map> // Can be used instead of large vector for mid_bucket if needed
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; // 10^8 + 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];
// Initialize DSU: each node is its own parent
void init_dsu() {
iota(parent + 1, parent + n + 1, 1); // Fill parent[i] = i for i from 1 to n
}
// Find the representative (root) of the set containing node v (with path compression)
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]); // Path compression
}
// Unite the sets containing nodes a and b
void unite_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
// Simple union: make one root point to the other.
// Union by rank/size could be used but often not critical here.
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];
int ans[MAXQ]; // Though L[i] will hold the final answer after loops
// Vector to store queries grouped by their 'mid' value in each iteration
// We use a vector of pairs (mid, query_index) and sort it instead of large array/map
vector<pair<int, int>> mid_query_pairs;
int main() {
// Faster I/O
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); // Store for later processing
}
// --- Read NPP locations and run Multi-Source Dijkstra ---
cin >> k;
vector<int> npp_cities(k);
// Priority queue for Dijkstra: {distance, city}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
// Initialize distances to infinity
fill(dist_npp + 1, dist_npp + n + 1, INF);
// Add all NPP cities to the priority queue with distance 0
for (int i = 0; i < k; ++i) {
cin >> npp_cities[i];
if (dist_npp[npp_cities[i]] == INF) { // Handle case if same city has multiple NPPs (problem says no)
dist_npp[npp_cities[i]] = 0;
pq.push({0, npp_cities[i]});
}
}
// Dijkstra algorithm
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
// If we found a shorter path already, skip
if (d > dist_npp[u]) continue;
// Relax edges
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); // Reserve space
int max_possible_threshold = 0; // Track the maximum threshold seen
for(const auto& edge_tuple : raw_edges) {
int u, v, w;
tie(u, v, w) = edge_tuple;
// Calculate threshold, handle potential INF distances (though graph is connected)
long long threshold_ll = min(dist_npp[u], dist_npp[v]);
int threshold_int = (threshold_ll >= MAX_DIST_THRESHOLD) ? MAX_DIST_THRESHOLD : (int)threshold_ll;
if (threshold_ll == INF) threshold_int = 0; // Or handle appropriately if unreachable from NPP is possible
edges.push_back({u, v, threshold_int});
max_possible_threshold = max(max_possible_threshold, threshold_int);
}
// Sort edges by threshold in descending order
sort(edges.begin(), edges.end(), compareEdges);
// --- 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; // Lower bound for dangerousness
R[i] = max_possible_threshold + 1; // Upper bound (exclusive)
}
// --- Parallel Binary Search ---
// We perform a fixed number of iterations (logarithmic in the range of answers)
// log2(10^8) is roughly 27, so 30-35 iterations are safe.
for (int iter = 0; iter < 35; ++iter) {
init_dsu(); // Reset DSU for this iteration
mid_query_pairs.clear(); // Clear the list of mid-values to check
// Group queries by their mid-value for this iteration
for (int i = 0; i < Q; ++i) {
if (L[i] != R[i]) { // If the range hasn't converged
int mid = L[i] + (R[i] - L[i]) / 2;
mid_query_pairs.push_back({mid, i});
}
}
// If no queries left to process, break early
if (mid_query_pairs.empty()) break;
// Sort queries by their 'mid' value descending, to process them alongside edges
sort(mid_query_pairs.rbegin(), mid_query_pairs.rend()); // Sort descending by mid
int edge_idx = 0;
int mid_pair_idx = 0;
// Iterate through possible thresholds (mid values) from high to low implicitly via sorted lists
// This loop structure efficiently processes edges and queries together
for(const auto& edge : edges) {
int current_edge_threshold = edge.threshold;
// Process all queries whose 'mid' is >= the current edge's threshold
while(mid_pair_idx < mid_query_pairs.size() && mid_query_pairs[mid_pair_idx].first >= current_edge_threshold) {
int query_idx = mid_query_pairs[mid_pair_idx].second;
int mid = mid_query_pairs[mid_pair_idx].first;
int s = queries[query_idx].s;
int t = queries[query_idx].t;
// Check connectivity *at the state before adding the current edge*
// This check happens when the DSU includes all edges with threshold > mid
// (Or >= mid, depending on strictness needed - need >= mid)
// Check if s and t can be connected with dangerousness 'mid'
if (dist_npp[s] >= mid && dist_npp[t] >= mid && find_set(s) == find_set(t)) {
L[query_idx] = mid; // Possible to achieve 'mid', try higher or equal
} else {
R[query_idx] = mid; // Not possible to achieve 'mid', must try lower
}
mid_pair_idx++;
}
// Add the current edge to the DSU
unite_sets(edge.u, edge.v);
}
// Process any remaining queries (those with mid < smallest edge threshold, or mid=0)
// These queries are checked against the DSU state after all edges have been added.
while(mid_pair_idx < mid_query_pairs.size()) {
int query_idx = mid_query_pairs[mid_pair_idx].second;
int mid = mid_query_pairs[mid_pair_idx].first;
int s = queries[query_idx].s;
int t = queries[query_idx].t;
// Check connectivity in the fully merged DSU (for edges relevant to the threshold)
if (dist_npp[s] >= mid && dist_npp[t] >= mid && find_set(s) == find_set(t)) {
L[query_idx] = mid;
} else {
R[query_idx] = mid;
}
mid_pair_idx++;
}
} // End of binary search iterations
// --- Output Results ---
// After the iterations, L[i] holds the maximum 'mid' for which the check succeeded,
// which is the maximal dangerousness.
for (int i = 0; i < Q; ++i) {
cout << L[i] << "\n";
}
return 0;
}
