include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

struct Edge { int u, v; long long p, q, d; };

struct NodeEdge { int to; long long w; };

int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);

int n, m, k;
if (!(cin >> n >> m >> k)) return 0;

vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
    cin >> edges[i].u >> edges[i].v >> edges[i].p >> edges[i].q;
    edges[i].d = edges[i].q - edges[i].p;
}

// Sắp xếp các cạnh theo độ chênh lệch d = q - p tăng dần
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
    return a.d < b.d;
});

vector&lt;pair&lt;int, int>> queries(k);
vector<int> srcs;
for (int i = 0; i < k; i++) {
    cin >> queries[i].first >> queries[i].second;
    srcs.push_back(queries[i].first);
    srcs.push_back(queries[i].second);
}

// Lọc các đỉnh duy nhất từ các truy vấn để giảm thiểu số lần chạy Dijkstra
sort(srcs.begin(), srcs.end());
srcs.erase(unique(srcs.begin(), srcs.end()), srcs.end());
int num_srcs = srcs.size();

// Hàm lấy ID đã nén của đỉnh
auto get_id = [&](int u) {
    return lower_bound(srcs.begin(), srcs.end(), u) - srcs.begin();
};

// dist[i][u] là khoảng cách ngắn nhất từ đỉnh nguồn thứ i đến đỉnh u
vector&lt;vector&lt;long long>> dist(num_srcs, vector&lt;long long>(n + 1, INF));
for (int i = 0; i < num_srcs; i++) {
    dist[i][srcs[i]] = 0;
}

vector<vector<NodeEdge>> adj(n + 1);
vector&lt;long long> ans(k, INF);

for (const auto& e : edges) {
    int u = e.u;
    int v = e.v;
    long long p = e.p;
    long long q = e.q;

    // 1. Cập nhật đáp án cho các truy vấn với giả định cạnh hiện tại là cạnh bị tắc đường (q lớn nhất)
    for (int i = 0; i < k; i++) {
        int s = queries[i].first;
        int t = queries[i].second;
        int id_s = get_id(s);
        int id_t = get_id(t);

        if (dist[id_s][u] != INF && dist[id_t][v] != INF) {
            ans[i] = min(ans[i], dist[id_s][u] + q + dist[id_t][v]);
        }
        if (dist[id_s][v] != INF && dist[id_t][u] != INF) {
            ans[i] = min(ans[i], dist[id_s][v] + q + dist[id_t][u]);
        }
    }

    // 2. Thêm cạnh vào đồ thị với trọng số bình thường p
    adj[u].push_back({v, p});
    adj[v].push_back({u, p});

    // 3. Cập nhật khoảng cách động (Incremental Dijkstra) cho các nguồn
    for (int i = 0; i < num_srcs; i++) {
        priority_queue&lt;pair&lt;long long, int>, vector&lt;pair&lt;long long, int>>, greater&lt;pair&lt;long long, int>>> pq;
        bool updated = false;

        // Đẩy vào hàng đợi nếu cạnh mới tạo ra đường đi ngắn hơn
        if (dist[i][u] + p < dist[i][v]) {
            dist[i][v] = dist[i][u] + p;
            pq.push({dist[i][v], v});
            updated = true;
        }
        if (dist[i][v] + p < dist[i][u]) {
            dist[i][u] = dist[i][v] + p;
            pq.push({dist[i][u], u});
            updated = true;
        }

        // Chỉ chạy lan truyền nếu có sự cập nhật
        if (updated) {
            while (!pq.empty()) {
                auto [d_curr, curr] = pq.top();
                pq.pop();

                if (d_curr > dist[i][curr]) continue;

                for (const auto& next_edge : adj[curr]) {
                    int nxt = next_edge.to;
                    long long w = next_edge.w;

                    if (dist[i][curr] + w < dist[i][nxt]) {
                        dist[i][nxt] = dist[i][curr] + w;
                        pq.push({dist[i][nxt], nxt});
                    }
                }
            }
        }
    }
}

for (int i = 0; i < k; i++) {
    cout << ans[i] << '\n';
}

return 0;

}

// I Love yomom

include <bits/stdc++.h>

define ll long long

define fi first

define se second

using namespace std;

const ll N = 1005, inf = 1e18;

ll n, m, k; struct data { ll u, v, p, q, d; } ed[N]; struct _data1 { ll u, v, w; }; pair<ll, ll> ques[N]; vector<_data1> adj[N]; namespace sub4 { ll dl[N][N], dr[N][N], ans[11]; priorityqueue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pql[N], pqr[N];

void dijkstra(ll s, ll (&d)[N][N], priorityqueue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> (&pq)[N]) { while (!_pq[s].empty()) { ll u = _pq[s].top().se; ll l = _pq[s].top().fi; _pq[s].pop(); if (l > d[s][u]) continue; for (auto v : adj[u]) { if (d[s][v.v] > d[s][u] + v.w) _pq[s].push({d[s][v.v] = d[s][u] + v.w, v.v}); } } } void solve() { for (ll i = 1; i <= n; i++) { dl[i][i] = dr[i][i] = 0, pql[i].push({0, i}), pqr[i].push({0, i}); for (ll j = 1; j <= n; j++) { if (i != j) dl[i][j] = dr[i][j] = inf; } } for (ll qu = 1; qu <= k; qu++) ans[qu] = inf;

sort(ed + 1, ed + 1 + m, [&](_data x, _data y) { return x.d < y.d; });

for (ll i = 1; i <= m; i++) {
    ll u = ed[i].u, v = ed[i].v, p = ed[i].p, q = ed[i].q;

    for (ll qu = 1; qu <= k; qu++) {
        ll s = ques[qu].fi, t = ques[qu].se;
        if (dl[s][u] != inf and dr[t][v] != inf)
            ans[qu] = min(ans[qu], dl[s][u] + q + dr[t][v]);
        if (dl[s][v] != inf and dr[t][u] != inf)
            ans[qu] = min(ans[qu], dl[s][v] + q + dr[t][u]);
    }

    adj[u].push_back({v, p});
    adj[v].push_back({u, p});
    for (ll qu = 1; qu <= k; qu++) {
        if (dl[ques[qu].fi][v] > dl[ques[qu].fi][u] + p) {
            pql[ques[qu].fi].push({dl[ques[qu].fi][v] = dl[ques[qu].fi][u] + p, v});
            dijkstra(ques[qu].fi, dl, pql);
        }
        if (dl[ques[qu].fi][u] > dl[ques[qu].fi][v] + p) {
            pql[ques[qu].fi].push({dl[ques[qu].fi][u] = dl[ques[qu].fi][v] + p, u});
            dijkstra(ques[qu].fi, dl, pql);
        }

        if (dr[ques[qu].se][v] > dr[ques[qu].se][u] + p) {
            pqr[ques[qu].se].push({dr[ques[qu].se][v] = dr[ques[qu].se][u] + p, v});
            dijkstra(ques[qu].se, dr, pqr);
        }
        if (dr[ques[qu].se][u] > dr[ques[qu].se][v] + p) {
            pqr[ques[qu].se].push({dr[ques[qu].se][u] = dr[ques[qu].se][v] + p, u});
            dijkstra(ques[qu].se, dr, pqr);
        }
    }
}
for (ll qu = 1; qu <= k; qu++) {
    cout << ans[qu] << '\n';
}

} } main() { cin.tie(0)->syncwithstdio(0); cin >> n >> m >> k; for (ll i = 1; i <= m; i++) { ll u, v, p, q; cin >> u >> v >> p >> q; ed[i] = {u, v, p, q, q - p}; } for (ll i = 1; i <= k; i++) { cin >> ques[i].fi >> ques[i].se; } sub4::solve(); }