#include <bits/stdc++.h> using namespace std; #define pb push_back #define int long long const int MOD = 1e9 + 7; const int INF = 1e15; const int N = 1e6; int n, m, k, a, b, c, d, h, l, r, p, q, u, v, x, y; vector<int> arr(N); vector<int> adj[N]; vector<int> vis(N); vector<int> depths(N); map<pair<int, int>, int> weight; vector<int> id(N); vector<int> indeg(N, -1); vector<int> component; void dfs(int node, int dist) { vis[node] = true; component.pb(node); if(dist > x) { x = dist; y = node; } // cout << node << " "; for(auto j : adj[node]) { if(!vis[j]) { dfs(j, dist+weight[{node, j}]); } } } void line() { l = 1; for(int i = 0; i<n; i++) { if(!vis[i] && indeg[i]==-1) { x = 0; y = i; component.clear(); dfs(i, 0); for(auto j : component) { id[j] = l; // cout << j << " "; } // cout << "\n"; h = 0; while(indeg[y]!=-1) { h += weight[{y, indeg[y]}]; y = indeg[y]; depths[y] = h; } l++; } } // for(int i = 0; i<n; i++) cout << depths[i] << " "; // cout << "\n"; while(q--) { cin >> a >> b; // cout << id[a] << " " << id[b] << " "; if(id[a] != id[b] || depths[a] < depths[b]) { cout << -1 << "\n"; continue; } else { cout << depths[a]-depths[b] << "\n"; } } } void solve() { cin >> k >> n >> m >> q; bool sub2 = true; for(int i = 1; i<=m; i++) { cin >> a >> b >> c; if(a!=0) { sub2 = false; } adj[a].pb(b); weight[{a, b}] = c; weight[{b, a}] = c; indeg[b] = a; } if(k==1) { line(); return; } while(q--) { cin >> a >> b; vector<int> dist(n, INF); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que; que.push({0, a}); dist[a] = 0; while(!que.empty()) { d = que.top().first; a = que.top().second; que.pop(); if(d>dist[a])continue; for(auto j : adj[a]) { if(dist[a]+weight[{a, j}] < dist[j]) { dist[j] = dist[a] + weight[{a, j}]; que.push({dist[j], j}); } } } if(dist[b] == INF) cout << -1; else cout << dist[b]; cout << "\n"; } } int32_t main() { ios::sync_with_stdio(false); cout.tie(0); cin.tie(0); int tc = 1; while(tc--) { solve(); } return 0; }