#include <iostream>
#include <vector>
#include <cstdio>

#define int long long
class solution {
private:
    std::vector<std::vector<long long>> graph;
    long long n;
    int m;
    int k;
    int q;
public:

    solution() {
        std::cin >> n >> m >> k;

        graph = std::vector<std::vector<long long>>(n, std::vector<long long>(n, INT64_MAX));

        for (int i = 0; i < m; i++) {
            int a;
            int b;
            int w;

            std::cin >> a >> b >> w;
            a--;
            b--;
            graph[a][b] = w;
        }
    }

    void floyd_condition() {
        for (int mid = 0; mid < n; mid++) {
            for (int from = 0; from < n; from++) {
                for (int to = 0; to < n; to++) {
                    if (graph[from][mid] != INT64_MAX && graph[mid][to] != INT64_MAX) {
                        if (std::abs(from - mid) <= k && std::abs(to - mid) <= k) {
                            graph[from][to] = std::min(graph[from][to], graph[from][mid] + graph[mid][to]);
                        }
                    }
                }
            }
        }
    }

    void answer() {
        std::cin >> q;
        while (q--) {
            int a;
            int b;
            std::cin >> a >> b;
            a--;
            b--;
            int ans = graph[a][b];
            if (ans == INT64_MAX) {
                ans = -1;
            }
            std::cout << ans << '\n';
        }
    }
};

signed main() {
    solution sol;
    sol.floyd_condition();
    sol.answer();
    return 0;
}