#include <climits>
#include <iostream>
#include <vector>

struct Edge {
    Edge(int f, int t, int c, int tm) {
        from = f;
        to = t;
        cost[0] = c;
        cost[1] = tm;
    }
    int from, to, cost[2];
};

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);

    std::vector<Edge> edges;
    int n, m, k;
    while (std::cin >> n >> m && n != 0 && m != 0) {
        for (int i = 0; i < n; i++) {
            int from, to, cost, time;
            std::cin >> from >> to >> cost >> time;
            edges.push_back(Edge(from - 1, to - 1, cost, time));
        }

        std::cin >> k;
        for (int i = 0; i < k; i++) {
            auto sts = new int[m]();
            auto used = new bool[m]();
            for (int j = 0; j < m; j++) {
                sts[j] = INT_MAX;
                used[j] = false;
            }

            int start, end, query;
            std::cin >> start >> end >> query;

            int cur = start - 1;
            sts[cur] = 0;
            used[cur] = true;
            while (!used[end - 1]) {
                for (auto e : edges) {
                    if (e.to == cur && sts[e.from] > sts[cur] + e.cost[query])
                        sts[e.from] = sts[cur] + e.cost[query];
                    if (e.from == cur && sts[e.to] > sts[cur] + e.cost[query])
                        sts[e.to] = sts[cur] + e.cost[query];
                }
                for (int j = 0; j < m; j++) std::cout << sts[j] << ' ';
                std::cout << std::endl;

                int min_i, min_c = INT_MAX;
                for (int j = 0; j < m; j++)
                    if (!used[j] && min_c > sts[j]) {
                        min_i = j;
                        min_c = sts[j];
                    }
                used[min_i] = true;
                cur = min_i;
            }
            std::cout << sts[end - 1] << std::endl;
            delete[] sts;
            delete[] used;
        }
        edges.clear();
    }
}