Go: // Warshall–Floyd Algorithm

package main

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

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
					c_prev[i][j] = -1
				} else {
					c_dist[i][j] = c_matrix[i][j]
					c_prev[i][j] = i
				}
				if t_matrix[i][j] == 0 {
					t_dist[i][j] = INF
					t_prev[i][j] = -1
				} else {
					t_dist[i][j] = t_matrix[i][j]
					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<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cctype>

#define mp make_pair
#define pb push_back
#define REP(i,a,n) for(int i = a;i < (n);i++)
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define range(x,min,max) ((min) <= (x) && (x) <= (max)) 

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<vector<int> > VII;
typedef pair<int,int> PII;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int n,m;
VI A,B;
VII C(2);

int dijkstra(int s,int g,int mode){
	VI dist(m + 1,INT_MAX);
	priority_queue<PII,vector<PII >,greater<PII > > que;
	que.push(mp(0,s));
	dist[s] = 0;
	while(!que.empty()){
		int d = que.top().first, u = que.top().second;
		que.pop();
		if(dist[u] < d) continue;
		rep(i,n){
			if(u == A[i] && dist[u] + C[mode][i] < dist[B[i]]){
				dist[B[i]] = dist[u] + C[mode][i];
				que.push(mp(dist[B[i]],B[i]));
			}
			if(u == B[i] && dist[u] + C[mode][i] < dist[A[i]]){
				dist[A[i]] = dist[u] + C[mode][i];
				que.push(mp(dist[A[i]],A[i]));
			}
		}
	}
	return dist[g];
}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	while(1){
		A.clear();
		B.clear();
		C[0].clear();
		C[1].clear();
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		
		rep(i,n){
			int a,b,c,t;
			cin >> a >> b >> c >> t;
			A.pb(a);
			B.pb(b);
			C[0].pb(c);
			C[1].pb(t);
		}
		int k;
		cin >> k;
		rep(i,k){
			int s,g,mode;
			cin >> s >> g >> mode;
			int ans = dijkstra(s,g,mode);
			cout << ans << endl;
		}
	}
	return 0;
}

C++: #include<iostream>
#include<queue>
#include<algorithm>
#include<utility>
#include<vector>
#include<climits>
using namespace std;

#define MAX_M 110

struct edge{int to,cost;};
typedef pair<int,int> P;

vector<edge> c[2][MAX_M];

int dijkstra(int s,int e,bool r){
	int d[MAX_M];
	for(int i=0;i<MAX_M;i++){
		d[i]=INT_MAX;
	}
	priority_queue<P,vector<P>,greater< P > > que;
	
	d[s]=0;
	
	que.push(P(0,s));
	
	while(!que.empty()){
		P p=que.top();que.pop();
		int v=p.second;
		if(d[v]<p.first) continue;
		for(int i=0;i<c[r][v].size();i++){
			edge e=c[r][v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
	
	return d[e];
}

int main(){
	int n,m;
	while(cin>>n>>m,n!=0||m!=0){
		for(int r=0;r<2;r++){
			for(int i=0;i<MAX_M;i++){
				c[r][i].clear();
			}
		}
		for(int i=0;i<n;i++){
			int a,b,cos,tim;
			cin>>a>>b>>cos>>tim;
			edge co,t;
			co.to=b;co.cost=cos;
			t.to=b;t.cost=tim;
			c[0][a].push_back(co);
			c[1][a].push_back(t);
		}
		int k;
		cin>>k;
		for(int i=0;i<k;i++){
			int s,e;
			bool r;
			cin>>s>>e>>r;
			int ans=dijkstra(s,e,r);
			cout<<ans<<endl;
		}
	}
}

C++: #include <vector>
#include <cstdio>

using namespace std;

#define M 100
#define INF 10e6

#define MIN(X,Y) ((X)<(Y)?(X):(Y))

int main(void){
    int n,m, qNum;
    int cost[M][M], tm[M][M];
    
    while (scanf("%d%d", &n,&m), n){
        // reset table
        for (int i=0; i<m; i++){
            for (int j=0; j<m; j++){
                cost[i][j] = tm[i][j] = INF;
            }
        }
        // read data
        for (int i=0; i<n; i++){
            int s,d,c,t;
            scanf("%d%d%d%d", &s, &d, &c, &t);
            s--; d--;
            cost[s][d] = cost[d][s] = c;
            tm[s][d] = tm[d][s] = t;
        }
        // warshall-floyd
        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]);
                    tm[i][j] = MIN(tm[i][j],tm[i][k]+tm[k][j]);                    
                }
            }
        }
        scanf("%d", &qNum);
        for (int i=0; i<qNum; i++){
            int s, d, type;
            scanf("%d%d%d", &s, &d, &type);
            s--; d--;
            printf("%d\n", type==0?cost[s][d]:tm[s][d]);
        }
    }
    
    return 0;
}