#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <numeric>
#include <iomanip>
#include <cassert>

typedef long long ll;
typedef double lf;
typedef unsigned long long ull;

using namespace std;

const int MAXN = 95;
const ll INF = 1e18;

int n, m; ll S;
ll e[MAXN][MAXN], c[MAXN][MAXN];

ll dis1[MAXN][MAXN]; bool vis[MAXN];
inline ll Calc(int u, int v, ll d)
{
    ll t = d % S;
    if (d <= c[u][v]) return d + e[u][v];
    return d - t + S + e[u][v];
}
inline void Dijkstra1(int s)
{
    for (int i = 0; i < n; i++) dis1[s][i] = INF, vis[i] = 0;
    dis1[s][s] = 0;
    for (int _ = 0; _ < n; _++)
    {
        int u = 0; ll mn = INF;
        for (int i = 0; i < n; i++)
            if (!vis[i] && mn > dis1[s][i]) u = i, mn = dis1[s][i];
        if (mn == INF) break;
        vis[u] = 1;
        for (int v = 0; v < n; v++)
            if (!vis[v]) dis1[s][v] = min(dis1[s][v], Calc(u, v, dis1[s][u]));
    }
}

ll dis2[MAXN][MAXN];
inline void Dijkstra2(int s)
{
    for (int i = 0; i < n; i++) dis2[s][i] = -INF, vis[i] = 0;
    dis2[s][s] = S;
    for (int _ = 0; _ < n; _++)
    {
        int u = 0; ll mx = -INF;
        for (int i = 0; i < n; i++)
            if (!vis[i] && mx < dis2[s][i]) u = i, mx = dis2[s][i];
        if (mx < 0) break;
        vis[u] = 1;
        for (int v = 0; v < n; v++)
            if (!vis[v]) dis2[s][v] = max(dis2[s][v], min(dis2[s][u] - e[u][v], c[u][v]));
    }
}

vector <ll> Tm[MAXN];
vector <vector <ll>> dis3[MAXN];
set <pair <ll, int>, greater <pair <ll, int>>> st;
int rk[MAXN][MAXN], tp[MAXN];
vector <pair <int, ll>> g[MAXN];
void DFS(vector <ll> &dis, int u)
{
    for (auto [v, w] : g[u])
        if (dis[v] > dis[u] + w)
        {
            if (c[u][rk[u][tp[u]]])
            {
                st.erase(make_pair(c[v][rk[v][tp[v]]] - dis[v], v));
                st.emplace(c[v][rk[v][tp[v]]] - dis[u] - w, v);
            }
            dis[v] = dis[u] + w, DFS(dis, v);
        }
}
void Build(vector <ll> &dis, int u)
{
    vis[u] = 1;
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i].first;
        if (vis[v] || dis[v] < dis[u] + g[u][i].second) swap(g[u][i], g[u].back()), g[u].pop_back();
        else Build(dis, v);
    }
}
inline void Insert(int s, int t, int u, int v)
{
    if (dis3[s][t][u] > dis3[s][t][v]) swap(u, v);
    if (dis3[s][t][u] + e[u][v] >= dis3[s][t][v]) return;
    g[u].emplace_back(v, e[u][v]), g[v].emplace_back(u, e[u][v]);
    DFS(dis3[s][t], u);
    memset(vis, 0, sizeof(vis));
    Build(dis3[s][t], s);
}

vector <ll> calculate_necessary_time(int N, int M, ll S, int Q, vector <int> A, vector <int> B, vector <ll> L, vector <ll> C, vector <int> U, vector <int> V, vector <ll> T)
{
    n = N, m = M, ::S = S;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) 
            e[i][j] = INF;
    for (int i = 0; i < m; i++) e[A[i]][B[i]] = e[B[i]][A[i]] = L[i], c[A[i]][B[i]] = c[B[i]][A[i]] = C[i] - L[i];
    for (int i = 0; i < n; i++) Dijkstra1(i);
    for (int i = 0; i < n; i++) Dijkstra2(i);
    for (int i = 0; i < n; i++)
    {
        iota(rk[i], rk[i] + n, 0);
        sort(rk[i], rk[i] + n, [&](int x, int y) { return c[i][x] > c[i][y]; });
    }
    // for (int i = 0; i < n; i++, cout << "\n")
    //     for (int j = 0; j < n; j++)
    //         cout << e[i][j] << ' ';
    // for (int i = 0; i < n; i++, cout << "\n")
    //     for (int j = 0; j < n; j++)
    //         cout << dis1[i][j] << ' ';
    // for (int i = 0; i < n; i++, cout << "\n")
    //     for (int j = 0; j < n; j++)
    //         cout << dis2[i][j] << ' ';
    for (int s = 0; s < n; s++)
    {
        for (int i = 0; i < n; i++) tp[i] = 0, g[i].clear();
        Tm[s].push_back(S), dis3[s].push_back(vector <ll>(n, INF));
        dis3[s][0][s] = 0, st.clear();
        for (int i = 0; i < n; i++) st.emplace(c[i][rk[i][tp[i]]] - dis3[s][0][i], i);
        for (int t = 0; st.size(); t++)
        {
            ll nxtT = st.begin() -> first;
            assert(nxtT < Tm[s][t]);
            if (nxtT < 0) break;
            Tm[s].push_back(nxtT), dis3[s].push_back(dis3[s].back());
            while (st.size() && st.begin() -> first >= nxtT)
            {
                int u = st.begin() -> second; st.erase(st.begin());
                if (c[u][rk[u][++tp[u]]]) st.emplace(c[u][rk[u][tp[u]]] - dis3[s][t + 1][u], u);
                Insert(s, t + 1, u, rk[u][tp[u] - 1]);
            }
        }
    }
    // for (int s = 0; s < n; s++)
    // {
    //     cout << "S " << s << ":\n";
    //     for (int i = 0; i < Tm[s].size(); i++)
    //     {
    //         cout << Tm[s][i] << ": ";
    //         for (int j = 0; j < n; j++) cout << dis3[s][i][j] << ' '; cout << "\n";
    //     }
    // }
    vector <ll> answer(Q);
    for (int i = 0; i < Q; i++)
    {
        int u = U[i], v = V[i]; ll t = T[i], ans = INF;
        for (int j = 0; j < n; j++)
            if (dis2[j][u] >= t) ans = min(ans, S - t + dis1[j][v]);
        int it = upper_bound(Tm[u].begin(), Tm[u].end(), t, greater <ll>()) - Tm[u].begin() - 1;
        // cout << ans << ' ' << dis3[u][it][v] << "\n";
        ans = min(ans, dis3[u][it][v]);
        answer[i] = ans;
    }
    return answer;
}

// #include "A.h"