#include<bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #define pb push_back #define eb emplace_back #define vi vector<int> #define vk vector #define vl vector<ll> #define pii pair<int,int> #define all(x) x.begin(),x.end() #define ld long double #define tt ll tcs; cin>>tcs; for(int i =0;i<tcs;i++) # define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector<vector<ll>> mul(vector<vector<ll>> &a,vector<vector<ll>>&b,int p) { vector<vector<ll>> c(p,vector<ll>(p,LLONG_MAX)); for(int i =0;i<p;i++) { for(int j =0;j<p;j++) { for(int k =0;k<p;k++) { if (a[i][k]!=LLONG_MAX&&b[k][j]!=LLONG_MAX) { c[i][j]=min(a[i][k]+b[k][j],c[i][j]); } } } } return c; } void solve() { int k,m,n,o; cin>>k>>n>>m>>o; int n_ = (n + k - 1) / k; int len = ceil(log2(n_)); vector<vector<vector<vector<ll>>>> vm(n_,vector<vector<vector<ll>>>(len+1)); for (int i = 0 ; i < n_ ; i++) { for (int j = 0 ; j <=len ; j++) { vm[i][j] = vector<vector<ll>>(k,vector<ll>(k,LLONG_MAX)); } } for(int i =0;i<m;i++) { int a,b,t; cin>>a>>b>>t; vm[a/k][0][a%k][b%k]=t; } for (int i = 0;i<n_;i++) { for (int j = 1;j<=len;j++) { if (i+(1<<(j-1))<n_) { vm[i][j] = mul(vm[i][j-1],vm[i+(1<<(j-1))][j-1],k); } } } while (o--) { int a,b; cin>>a>>b; int s = a/k; int t = b/k; int tim = t-s; vector<vector<ll>> vv(k,vector<ll>(k,LLONG_MAX)); for(int i =0;i<k;i++) vv[i][i]=0; while (tim>0) { int p = 31-__builtin_clz(tim); vv = mul(vv,vm[s][p],k); tim-=(1<<p); s+=(1<<p); } if (vv[a%k][b%k]==LLONG_MAX) { vv[a%k][b%k]=-1; } cout<<vv[a%k][b%k]<<endl; } } int main() { FAST { solve(); } }