Go: // Warshall–Floyd Algorithm

package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

const INF = 0x7FFFFFFF

func main() {
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		n, _ := strconv.Atoi(buf[0])
		m, _ := strconv.Atoi(buf[1])
		if n == 0 && m == 0 {
			break
		}
		c_matrix := make([][]int, m)
		for i := range c_matrix {
			c_matrix[i] = make([]int, m)
		}
		t_matrix := make([][]int, m)
		for i := range t_matrix {
			t_matrix[i] = make([]int, m)
		}
		for i := 0; i < n; i++ {
			scanner.Scan()
			buf_ := strings.Split(scanner.Text(), " ")
			a, _ := strconv.Atoi(buf_[0])
			b, _ := strconv.Atoi(buf_[1])
			c, _ := strconv.Atoi(buf_[2])
			t, _ := strconv.Atoi(buf_[3])
			c_matrix[a-1][b-1] = c
			t_matrix[a-1][b-1] = t
		}
		c_dist := make([][]int, m)
		c_prev := make([][]int, m)
		t_dist := make([][]int, m)
		t_prev := make([][]int, m)
		for i := 0; i < m; i++ {
			c_dist[i] = make([]int, m)
			c_prev[i] = make([]int, m)
			t_dist[i] = make([]int, m)
			t_prev[i] = make([]int, m)
		}
		for i := 0; i < m; i++ {
			for j := 0; j < m; j++ {
				if c_matrix[i][j] == 0{
					c_dist[i][j] = INF
				} else {
					c_dist[i][j] = c_matrix[i][j]
				}
				if c_matrix[i][j] == 0{
					c_prev[i][j] = -1
				} else {
					c_prev[i][j] = i
				}
				if t_matrix[i][j] == 0{
					t_dist[i][j] = INF
				} else {
					t_dist[i][j] = t_matrix[i][j]
				}
				if t_matrix[i][j] == 0{
					t_prev[i][j] = -1
				} else {
					t_prev[i][j] = i
				}
			}
			c_dist[i][i] = 0
			t_dist[i][i] = 0
		}
		for k := 0; k < m; k++ {
			for i := 0; i < m; i++ {
				for j := 0; j < m; j++ {
					c_newlen := c_dist[i][k] + c_dist[k][j]
					if c_newlen < c_dist[i][j] {
						c_dist[i][j] = c_newlen
						c_prev[i][j] = c_prev[k][j]
					}
				}
			}
		}
		for k := 0; k < m; k++ {
			for i := 0; i < m; i++ {
				for j := 0; j < m; j++ {
					t_newlen := t_dist[i][k] + t_dist[k][j]
					if t_newlen < t_dist[i][j] {
						t_dist[i][j] = t_newlen
						t_prev[i][j] = t_prev[k][j]
					}

				}
			}
		}
		scanner.Scan()
		k, _ := strconv.Atoi(scanner.Text())
		for i := 0; i < k; i++ {
			scanner.Scan()
			buf_ := strings.Split(scanner.Text(), " ")
			p, _ := strconv.Atoi(buf_[0])
			q, _ := strconv.Atoi(buf_[1])
			r, _ := strconv.Atoi(buf_[2])
			switch r {
			case 0: fmt.Println(c_dist[p-1][q-1])
			case 1: fmt.Println(t_dist[p-1][q-1])
			}
		}
	}
}

C++: #include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<complex>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

const int N = 211;
int dpcost[N][N];
int dptime[N][N];

int main(){
	
	A:;
	int n,m;
	cin>>n>>m;
	if(n==0)return 0;
	
	const int INF = 1000000000;
	
	rep(i,N)rep(j,N)dpcost[i][j]=dptime[i][j]=INF;
	rep(i,N)dpcost[i][i]=dptime[i][i]=0;
	
	rep(i,n){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		dpcost[a][b]=c;
		dpcost[b][a]=c;
		dptime[a][b]=d;
		dptime[b][a]=d;
	}
	
	
	reps(k,1,m+1)reps(i,1,m+1)reps(j,1,m+1){
		dpcost[i][j] = min(dpcost[i][j], dpcost[i][k]+dpcost[k][j]);
		dptime[i][j] = min(dptime[i][j], dptime[i][k]+dptime[k][j]);
	}
	
	
	int r;
	cin>>r;
	
	rep(i,r){
		int a,b,c;
		cin>>a>>b>>c;
		if(c==0)printf("%d\n",dpcost[a][b]);
		if(c==1)printf("%d\n",dptime[a][b]);
	}
	
	goto A;
}

C++: #include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define INF 1 << 20
#define MAX_M 101
using namespace std;

int main(){
  int n, m, a, b, c, t, p, q, r, s;  
  int C[MAX_M][MAX_M], T[MAX_M][MAX_M];
  while(true){
	scanf("%d %d", &n, &m);
	if((n | m) == 0){
	  break;
	}
	fill((int*) C, (int*)(C + lengthof(C)), INF);
	fill((int*) T, (int*)(T + lengthof(T)), INF);
	REP(i,n){
	  scanf("%d %d %d %d", &a, &b, &c, &t);
	  C[a][b] = C[b][a] = c;
	  T[a][b] = T[b][a] = t;
	}
	REP(k,m+1){
	  REP(i,m+1){
		REP(j,m+1){
		  C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
		  T[i][j] = min(T[i][j], T[i][k] + T[k][j]);
		}
	  }
	}
	scanf("%d", &s);
	REP(i,s){
	  scanf("%d %d %d", &p, &q, &r);
	  if(r == 0){
		printf("%d\n", C[p][q]);
	  }
	  else{
		printf("%d\n", T[p][q]);
	  }
	}
  }
  return 0;
}

C++: //青春の片道切符：：ワーシャルフロイド法

	/*for(int k=0;k<N;k++){//経由箇所(N<200)
		for(int i=0;i<N;i++){//スタート(N<200)
			for(int j=0;j<N;j++){//目的(N<200)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}*/


#include<iostream>
#include<string>
#include<queue>
#include<utility>
#include<algorithm>
#include<cctype>
using namespace std;

long long gc[110][110];
long long gt[110][110];
int n,m;

void warshallfroid(){
	for(int k=0;k<m;k++){//経由箇所(N<200)
		for(int i=0;i<m;i++){//スタート(N<200)
			for(int j=0;j<m;j++){//目的(N<200)
				gc[i][j]=min(gc[i][j],gc[i][k]+gc[k][j]);
				gt[i][j]=min(gt[i][j],gt[i][k]+gt[k][j]);
			}
		}
	}
}



int main(){
	
	while(cin>>n>>m,n||m/*n,mが両方0のときお終わり*/){
		for(int i=0;i<m;i++){//スタート(N<200)
			for(int j=0;j<m;j++){//目的(N<200)
				gc[i][j]=9999999;//初期化
				gt[i][j]=9999999;//初期化
			}
		}
	

	
	for(int i=0;i<n;i++){
		int a,b,c,t;
		cin>>a>>b>>c>>t;
		a--,b--;
		gc[a][b]=gc[b][a]=c;
		gt[a][b]=gt[b][a]=t;
	}
	warshallfroid();
	
	int k;
	cin>>k;
	for(int i=0;i<k;i++){
	int p,q,r;
		cin>>p>>q>>r;
		p--,q--;
		if(r==0)cout<<gc[p][q]<<endl;
		else cout<<gt[p][q]<<endl;
	}
	
	}

}

C++: #include <iostream>
#include <algorithm>
#define INF 1000000
using namespace std;
int cost[100][100];
int t[100][100];
int d[100];
int m;

void dcost(int s) {
	bool used[100];
	fill(used, used + 100, false);
	fill(d, d + 100, INF);
	d[s] = 0;
	while (1) {
		int v = -1;
		for (int u = 0; u < m; ++u) {
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		if (v == -1) break;
		used[v] = true;

		for (int u = 0; u < m; ++u) {
			d[u] = d[u] < d[v] + cost[v][u] ? d[u] : d[v] + cost[v][u];
		}
	}
}

void dtime(int s) {
	bool used[100];
	fill(used, used + 100, false);
	fill(d, d + 100, INF);
	d[s] = 0;
	while (1) {
		int v = -1;
		for (int u = 0; u < m; ++u) {
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		if (v == -1) break;
		used[v] = true;

		for (int u = 0; u < m; ++u) {
			d[u] = d[u] < d[v] + t[v][u] ? d[u] : d[v] + t[v][u];
		}
	}
}

int main() {
	int n, k, a, b, p, q, r;
	
	while (cin >> n >> m, !(n == 0 && m == 0)) {
		fill(cost[0], cost[100], INF);
		fill(t[0], t[100], INF);
		while (n--) {
			cin >> a >> b;
			a--; b--;
			cin >> cost[a][b] >> t[a][b];
			cost[b][a] = cost[a][b];
			t[b][a] = t[a][b];
		}
		cin >> k;
		while (k--) {
			cin >> p >> q >> r;
			p--; q--;
			if (r == 1) dtime(p);
			else dcost(p);
			cout << d[q] << endl;
		}
		
	}
	return 0;
}

C++: #include<stdio.h>
#define INF 10000000
int e1[100][100],e2[100][100];
int d[100];
bool used[100];
int m,n;
int p,q,r;
int k;
int i,j;
int a,b,t,c;
int v;
int mc,mt;

int min(int x,int y){
	if(x<=y)return x;
	else return y;
}

void solve(int s,int mo){
	for(j=0;j<m;j++){
		used[j]=false;
		d[j]=INF;
	}
	d[s]=0;
	while(true){
		v=-1;
		for(int u=0;u<m;u++)if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
		if(v==-1)break;
		used[v]=true;
		for(int u=0;u<m;u++){
			if(mo==0)d[u]=min(d[u],d[v]+e1[v][u]);
			if(mo==1)d[u]=min(d[u],d[v]+e2[v][u]);
		}
	}
}


int main(){
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)break;
		mt=INF;
		mc=INF;
		for(i=0;i<m;i++)for(j=0;j<m;j++){
			e1[i][j]=INF;
			e2[i][j]=INF;
		}
		for(i=0;i<n;i++){
			scanf("%d %d %d %d",&a,&b,&c,&t);
			e1[a-1][b-1]=c;
			e1[b-1][a-1]=c;
			e2[a-1][b-1]=t;
			e2[b-1][a-1]=t;
		}
		scanf("%d",&k);
		for(i=0;i<k;i++){
			scanf("%d %d %d",&p,&q,&r);
			solve(p-1,r);
			if(r==0)mc=min(mc,d[q-1]);
			if(r==1)mt=min(mt,d[q-1]);
		}
		if(mc==INF)mc=0;
		if(mt==INF)mt=0;
		printf("%d\n%d\n",mc,mt);
	}
}