#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int INF = 1 << 25;

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

	int n, m, query;
	while (cin >> n >> m , n) {
		int cost[101][101], time[101][101];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				cost[i][j] = (i == j) ? 0 : INF;
				time[i][j] = (i == j) ? 0 : INF;
			}
		}

		while (n--) {
			int a, b, c, t;
			cin >> a >> b >> c >> t;
			cost[a - 1][b - 1] = cost[b - 1][a - 1] = c;
			time[a - 1][b - 1] = time[b - 1][a - 1] = t;
		}

		for (int k = 0; k < m; k++) {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < m; j++) {
					cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
					time[i][j] = min(time[i][j], time[i][k] + time[k][j]);
				}
			}
		}

		cin >> query;
		while (query--) {
			int p, q, r;
			cin >> p >> q >> r;
			if (r == 0) {
				cout << cost[p - 1][q - 1] << endl;
			}
			else {
				cout << time[p - 1][q - 1] << endl;
			}
		}
	}
}
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> mato;
vector<int> a;

int main(){
	int n,m;
	int self;
	while(scanf("%d %d",&n,&m) && n && m){
		mato.clear();
		a.clear();
		
		for(int i=0;i<n;i++){
			scanf("%d",&self);
			mato.push_back(self);
		}
		mato.push_back(0);
		sort(mato.begin(),mato.end());
		mato.erase(unique(mato.begin(),mato.end()),mato.end());
		int size = mato.size();
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				a.push_back(mato[i] + mato[j]);
			}
		}
		sort(a.begin(),a.end());
		a.erase(unique(a.begin(),a.end()),a.end());
		int max = 0;
		size = a.size();
		int s,ss;
		for(int i=0;i<size;i++){
			s = m - a[i];
			if(s > 0){
				ss = *(lower_bound(a.begin(),a.end(),s) - 1);
				//printf("find:%d -> %d\n",s,ss);
				if(a[i] + ss > max){ max = a[i] + ss; }
			}
		}
		printf("%d\n",max);
	}
}