#include <iostream>
#include <cstdio>
using namespace std;

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)

int N,M;
int maze[100][100],tim[100][100];
int main(void){
	while(cin>>N>>M,N+M){
	rep(i,M)rep(j,M)maze[i][j] = (1<<20),tim[i][j] = (1<<20);
	while(N--){
		int a,b,c,t;
		cin>>a>>b>>c>>t;
		maze[--a][--b] = c;
		tim[a][b] = t;
	}
	cout<<endl;
	rep(k,M){
		rep(i,M){
			rep(j,M){
				if(maze[i][j] > maze[i][k] + maze[k][j]){
					// update
					maze[i][j] = maze[i][k] + maze[k][j];
					tim[i][j] = min(tim[i][j],tim[i][k] + tim[k][j]);
				} 
			}
		}
	}
	rep(i,M)rep(j,M)cout<<tim[i][j]<<(j==M-1?'\n':' ');
	cin>>N;
	while(N--){
		int a,b,t;
		cin>>a>>b>>t;
		cout<<(t?tim[--a][--b]:maze[--a][--b])<<endl;
	}
}
}