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 <iostream>
#include <algorithm>
using namespace std;
const int INF = 1000000;
int cost[301][301],ttime[301][301];
int main(){
	int n,m;
	while(cin >> n >> m,n || m){
		int a,b,icost,itime,c,r;
		for(int i = 0;i <= m;++i){
			for(int j = 0;j <= m;++j){
				if(i == j) {
					cost[i][i] = 0;
					ttime[i][i] = 0;
				}
				else {
					cost[i][j] = INF;
					ttime[i][j] = INF;
				}
			}
		}
		for(int i = 0;i < n;++i){
			cin >> a >> b >> icost >> itime;
			cost[a][b] = cost[b][a] = icost;
			ttime[a][b] = ttime[b][a] = itime;
		}
		cin >> c;
		for(int d = 0;d < c;++d){
			cin >> a >> b >> r;
			for(int k = 0;k <= m;++k){
				for(int i = 0;i <= m;++i){
					for(int j = 0;j <= m;++j){
						if(r == 1) ttime[i][j] = min(ttime[i][j],ttime[i][k] + ttime[k][j]);
						else cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j]);
					}
				}
			}
			if(r == 1) cout << ttime[a][b] << endl;
			else cout << cost[a][b] << endl;
		}
	}
	return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;


int dpt[111][111];
int dpc[111][111];
int n, m, a, b, cost, t, k, p, q, r;

int main(){
	while (cin >> n >> m&&n + m){
		REP(i, 111){
			REP(j, 111){
				dpt[i][j] = INF;
				dpc[i][j] = INF;
			}
		}
		REP(i, n){
			cin >> a >> b >> cost >> t;
			dpt[a][b] = min(dpt[a][b], t);
			dpt[b][a] = min(dpt[a][b], t);
			dpc[a][b] = min(dpc[a][b], cost);
			dpc[b][a] = min(dpc[a][b], cost);
		}
		FOR(l, 1, m + 1){
			FOR(i, 1, m + 1){
				FOR(j, 1, m + 1){
					dpt[i][j] = min(dpt[i][j], dpt[i][l] + dpt[l][j]);
					dpc[i][j] = min(dpc[i][j], dpc[i][l] + dpc[l][j]);
				}
			}
		}
		cin >> k;
		REP(i, k){
			cin >> p >> q >> r;
			if (r == 0)cout << dpc[p][q] << endl;
			else cout << dpt[p][q] << endl;
		}
	}
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)

const int INF = 10000000;
const int MAX_V = 1000;
int graph[2][MAX_V][MAX_V];
int n, m;

bool visited[MAX_V];
int cost[MAX_V];

void init_graph() {
    REP(h, 2) {
        REP(i, m) {
            REP(j, m) {
                if (i == j) graph[h][i][j] = 0;
                else        graph[h][i][j] = INF;
            }
        }
    }
}

void make() {
    REP(i, n) {
        int u, v, c, t;
        scanf("%d %d %d %d", &u, &v, &c, &t);
        u--; v--;
        graph[0][u][v] = c; graph[0][v][u] = c;
        graph[1][u][v] = t; graph[1][v][u] = t;
    }
}

void init_dijkstra() {
    REP(i, MAX_V) visited[i] = false;
    REP(i, MAX_V) cost[i] = INF;
}

void dijkstra(int start, int g[MAX_V][MAX_V]) {
    init_dijkstra();

    cost[start] = 0;

    while (true) {
        int mi = INF;
        int nxt = -1;
        visited[start] = true;
        REP(i, m) {
            if (visited[i]) continue;
            if (i != start) {
                int d = cost[start] + g[start][i];
                if (d < cost[i]) {
                    cost[i] = d;
                }
            }
            if (mi > cost[i]) {
                mi = cost[i];
                nxt = i;
            }
        }
        start = nxt;
        if (nxt == -1) break;
    }
}

void solve() {
    while (true) {
        scanf("%d %d", &n, &m);

        if (n == 0 && m == 0) break;

        init_graph();

        make();

        int k;
        scanf("%d", &k);

        REP(i, k) {
            int p, q, r;
            scanf("%d %d %d", &p, &q, &r);
            p--; q--;
            dijkstra(p, graph[r]);
            printf("%d\n", cost[q]);
        }
    }
}

int main() {
    solve();
    return 0;
}

C++: #include<iostream>
#include<vector>
#include<queue>

using namespace std;

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

struct Edge {
  int to, cost[2];
};

int main() {
  while (true) {
    int n, m;
    cin >> n >> m;
    if (n == 0 && m == 0) break;
    int a, b, c, t;
    vector<Edge> edge[m];
    rep (i, n) {
      cin >> a >> b >> c >> t;
      --a;
      --b;
      Edge e;
      e.to = b;
      e.cost[0] = c;
      e.cost[1] = t;
      edge[a].push_back(e);
      e.to = a;
      edge[b].push_back(e);
    }
    int k;
    cin >> k;
    rep (iii, k) {
      int p, q, r;
      cin >> p >> q >> r;
      --p;
      --q;
      vector<int> dis;
      rep (i, m) dis.push_back(1e9);
      priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
      que.push(make_pair(0, p));
      while (!que.empty()) {
	pair<int, int> now = que.top();
	que.pop();
	if (dis[now.second] <= now.first) continue;
	dis[now.second] = now.first;
	rep (i, edge[now.second].size()) {
	  que.push(make_pair(edge[now.second][i].cost[r] + now.first, edge[now.second][i].to));
	}
      }
      cout << dis[q] << endl;
    }
  }
  return 0;
}