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 <iostream>
# include <vector>
# include <queue>
# include <functional>

constexpr int MAX_N = 100;
constexpr int INF = 100000000;

typedef std::pair<int, int> P;

struct edge {
	int to, cost;
	edge(int t, int c) : to(t), cost(c) {}
};

int n, m, K;
std::vector<edge> G[2][MAX_N];
int d[MAX_N];

void dijkstra(int s, int r) {
	std::fill(d, d + n, INF);
	d[s] = 0;
	std::priority_queue<P, std::vector<P>, std::greater<P>> que;
	que.push(P(d[s], s));

	while (!que.empty()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if (p.first > d[v])
			continue;
		for (int i = 0; i < G[r][v].size(); ++i) {
			edge e = G[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));
			}
		}
	}
}

int main() {
	int a, b, c, t;
	while (1) {
		std::cin >> m >> n;
		if (m + n == 0)
			break;

		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < n; ++j)
				G[i][j].clear();
		}

		for (int i = 0; i < m; ++i) {
			std::cin >> a >> b >> c >> t;
			G[0][a - 1].push_back(edge(b - 1, c));
			G[0][b - 1].push_back(edge(a - 1, c));
			G[1][a - 1].push_back(edge(b - 1, t));
			G[1][b - 1].push_back(edge(a - 1, t));
		}
		std::cin >> K;
		int p, q, r;
		for (int i = 0; i < K; ++i) {
			std::cin >> p >> q >> r;
			dijkstra(p - 1, r);
			std::cout << d[q - 1] << std::endl;
		}
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define ll2(x, y) ll x, y; cin >> x >> y;
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

#define ma 12345678
int G[100][100][2] = {0};

signed main(void){
  int i, j, k;
  for(int testcase = 0;testcase >= 0;testcase++){
    int2(n, m);
    if(n == 0 && m == 0)break;

    rep(i, 100)rep(j, 100)rep(k, 2)G[i][j][k] = ma;
    rep(i, n){
      int a, b, c, t;
      scanf("%d%d%d%d", &a, &b, &c, &t);
      --a; --b;
      G[a][b][0] = c; G[b][a][0] = c;
      G[a][b][1] = t; G[b][a][1] = t;
    }

    int l;
    rep(l, 2)rep(k, m)rep(i, m)rep(j, m){
      G[i][j][l] = min(G[i][k][l] + G[k][j][l], G[i][j][l]);
    }
    
    int(k);
    for(;k--;){
      int3(p, q, r);
      --p; --q;
      printf("%d\n", G[p][q][r]);
    }


//*/

//*/ break;
  }
  return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;
#define REP(i,n) for (int i=0; i<(n); ++i)

struct edge {
    int from, to, cost, time;
};

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        vector<edge> edges;
        int a, b, v, u;
        REP(i,n) {
            cin >> a >> b >> v >> u;
            edges.push_back((edge){ a, b, v, u });
        }
        int d[2][101][101];
        REP(i,2) REP(j,101) REP(k,101) {
            d[i][j][k] = (j == k ? 0 : 1e8);
        }
        REP(i,101) REP(j,101) for (auto &e : edges) {
            d[0][j][e.to] = min(d[0][j][e.to], d[0][j][e.from] + e.cost);
            d[1][j][e.to] = min(d[1][j][e.to], d[1][j][e.from] + e.time);
        }
        int k, p, q, r;
        cin >> k;
        REP(i,k) {
            cin >> p >> q >> r;
            cout << d[r][p][q] << endl;
        }
    }
    return 0;
}