好题。首先我们考虑一天之内能到达的情况。我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ，使得在 $T$ 之前的时刻出发，都可以在当天到达 $t$ （这里要注意有可能一天之内到不了，也就是可能 $T < 0$ ）。

这个东西如何计算？首先有一种非常暴力的想法，我们每次加入一个当前连通块连出去的边，同时可能导致 $T$ 减小，然后重新跑一次最短路。考虑这样的复杂度，枚举点 $O(n)$ ，加边次数是 $O(n^2)$ ，每次跑最短路使用 dijkstra （这里显然 $O(n^2+m)$ 是优于 $O(m\log m)$ 的），复杂度就是 $O(n^5)$ 。看起来不太能跑过。

但是这提示我们可以去枚举那个卡着上界的边 $(u,v,l,c)$ ，因为 $T$ 必然是由中间某个边的关闭时间决定的。然后尝试用这条边来卡上界，具体来说求出 $u$ 开始时间为 $c-l$ ，反着走图，到达 $s$ 所需要的最小时间，以及求出 $v$ 开始时间为 $c$ ，走正图，到达 $t$ 所需的最小时间，这两个值可以用类 dijkstra 来做，复杂度 $O(n^2)$ ，由这两个值来更新最晚时间，同时也就得到了在某个时间之前从 $s$ 到 $t$ 的一条可能的最短路。这部分的复杂度 $O(n^4)$ 。

于是对所有卡上界的边都求出某个时间之前从 $s$ 到 $t$ 的一个可能的最短路后按出发时间最晚值排序后求一个后缀最小值，于是就可以通过在这里面 lower_bound 得到当天到达的时间。

然后考虑如何做在非当天走到的情况。不妨枚举一下第一天走到哪个点，于是问题就变成了从某个点出发，且时间为 $0$ ，到达另一个点的最短路径。不难发现这个东西必然是先走几个整天，然后最后再走某一天的一个前缀。我们不妨设 $dis[u][v]$ 为 $u$ 在出发时间为 $0$ 时一天内到达 $v$ 的最短路，如果到不了则是 $\infin$ 。这个东西可以和刚刚一样的用类 dijkstra 来做。然后我们建一个新图，把一天内能到达的两点 $u \to v$ 连一条权值为 $1$ 的边，于是两点在这个图上的最短路就是需要花费多少个整天，跑一次 Floyd 即可。于是我们就可以对任意一对 $u,v$ 求出出发时间为 $0$ 的时候的最短路了，具体来说我们枚举一个点 $k$ ，表示从 $u \to k$ 走整天，最后从 $k \to v$ 走一天的一段前缀。这部分复杂度 $O(n^3)$ 。

于是这道题就做完了。复杂度 $O(n^4 + nq)$ 。代码常数非常大，跑了 8.3s 。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "cassert"
#include "queue"
using namespace std;
#define MAXN 93
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , q;
ll s;
int A[MAXN];

ll L[MAXN][MAXN] , C[MAXN][MAXN];
ll W[MAXN][MAXN][2][MAXN];
ll dis[MAXN][MAXN];

int vis[MAXN];
void dijk( int s , ll cur , ll ds[MAXN] ) {
	rep( i , 1 , n ) vis[i] = 0 , ds[i] = 1e18;
	ds[s] = 0;
	while( 233 ) {
		pair<ll,int> mn = mp( 1e18 , 0 );
		rep( i , 1 , n ) if( !vis[i] ) mn = min( mn , mp( ds[i] , i ) );
		if( !mn.se ) return;
		int u = mn.se;
		vis[u] = 1;
		rep( v , 1 , n ) if( !vis[v] && C[u][v] - L[u][v] >= cur + ds[u] && ds[u] + L[u][v] < ds[v] ) 
			ds[v] = ds[u] + L[u][v];
	}
}

void dijk2( int s , ll cur , ll ds[MAXN] ) {
	rep( i , 1 , n ) vis[i] = 0 , ds[i] = 1e18;
	ds[s] = 0;
	while( 233 ) {
		pair<ll,int> mn = mp( 1e18 , 0 );
		rep( i , 1 , n ) if( !vis[i] ) mn = min( mn , mp( ds[i] , i ) );
		if( !mn.se ) return;
		int u = mn.se;
		vis[u] = 1;
		rep( v , 1 , n ) if( !vis[v] && C[v][u] >= cur - ds[u] && ds[u] + L[v][u] < ds[v] )
			ds[v] = ds[u] + L[v][u];
	}
}

ll lt[MAXN][MAXN];
vector<pair<ll,ll>> D[MAXN][MAXN];

int G[MAXN][MAXN];
ll ar[MAXN][MAXN];

void solve() {
	cin >> n >> m >> s >> q;
	memset( L , 0x3f , sizeof L );
	rep( i , 1 , m ) {
		int u , v;
		ll l , c;
		scanf("%d%d%lld%lld",&u,&v,&l,&c);
		++ u , ++ v;
		L[u][v] = L[v][u] = l , C[u][v] = C[v][u] = c;
	}
	memset( lt , -1 , sizeof lt );
	rep( u , 1 , n ) lt[u][u] = s;
	rep( u , 1 , n ) rep( v , 1 , n ) if( L[u][v] < 1e18 ) 
		dijk( u , C[u][v] , W[u][v][1] ) , dijk2( u , C[u][v] - L[u][v] , W[u][v][0] );
	rep( u , 1 , n ) rep( v , 1 , n ) {
		rep( s , 1 , n ) rep( t , 1 , n ) if( L[s][t] < 1e18 ) {
			ll ds = W[s][t][0][u] + L[s][t] + W[t][s][1][v] , tim = C[s][t] - L[s][t] - W[s][t][0][u];
			if( ds < 1e18 ) {
				lt[u][v] = max( lt[u][v] , tim );
				D[u][v].eb( mp( tim , ds ) );
			}
		}
		sort( all( D[u][v] ) );
		int s = D[u][v].size() - 1;
		per( i , s - 1 , 0 ) D[u][v][i].se = min( D[u][v][i].se , D[u][v][i + 1].se );
	}
	memset( G , 0x3f , sizeof G );
	rep( u , 1 , n ) {
		G[u][u] = 0;
		dijk( u , 0 , dis[u] );
		rep( v , 1 , n ) if( u != v && dis[u][v] < 1e18 ) G[u][v] = 1;
	}
	rep( k , 1 , n ) rep( i , 1 , n ) rep( j , 1 , n ) 
		G[i][j] = min( G[i][j] , G[i][k] + G[k][j] );
	memset( ar , 0x3f , sizeof ar );
	rep( u , 1 , n ) rep( v , 1 , n ) {
		ar[u][v] = dis[u][v];
		rep( k , 1 , n ) if( dis[k][v] < 1e18 )
			ar[u][v] = min( ar[u][v] , G[u][k] * s + dis[k][v] );
	}
	rep( i , 1 , q ) {
		int u , v; ll t;
		scanf("%d%d%lld",&u,&v,&t);
		++ u , ++ v;
		if( lt[u][v] >= t ) {
			printf("%lld\n",lower_bound( all( D[u][v] ) , mp( t , 0ll ) ) -> se);
		} else {
			ll as = 1e18;
			rep( k , 1 , n ) if( lt[u][k] >= t ) 
				as = min( as , s - t + ar[k][v] );
			printf("%lld\n",as);
		}
	}
	
}

signed main() {
//	freopen("input.txt","r",stdin) , freopen("ot","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}