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>
using namespace std;

#define INF 100000000

struct edge {
	int to;
	int c, t;
};

int main() {
	int n, m, f, temp, s, k, p, q, r;
	vector<edge> g[101];
	queue<int> search;
	int mc[101][101], mt[101][101];
	edge e;
	while(1) {
		cin >> n >> m;
		if(!n&&!m) break;
		for(int i=0; i<=m; ++i) g[i].clear();
		for(int i=0; i<=m; ++i) for(int j=0; j<=m; ++j) {
			mc[i][j] = mt[i][j] = INF;
		}
		for(int i=0; i<n; ++i) {
			cin >> f >> e.to >> e.c >> e.t;
			g[f].push_back(e);
			temp = e.to; e.to = f; f = temp;
			g[f].push_back(e);
		}
		for(int i=1; i<=m; ++i) {
			search.push(i); mc[i][i] = 0;
			while(!search.empty()) {
				s = search.front(); search.pop();
				for(vector<edge>::iterator it=g[s].begin(); it!=g[s].end(); ++it) {
					if(mc[i][s]+(*it).c<mc[i][(*it).to]) {
						mc[i][(*it).to] = mc[i][s]+(*it).c;
						search.push((*it).to);
					}
				}
			}
			search.push(i); mt[i][i] = 0;
			while(!search.empty()) {
				s = search.front(); search.pop();
				for(vector<edge>::iterator it=g[s].begin(); it!=g[s].end(); ++it) {
					if(mt[i][s]+(*it).t<mt[i][(*it).to]) {
						mt[i][(*it).to] = mt[i][s]+(*it).t;
						search.push((*it).to);
					}
				}
			}
		}
		cin >> k;
		for(int i=0; i<k; ++i) {
			cin >> p >> q >> r;
			if(!p&&!q) break;
			cout << (!r?mc[p][q]:mt[p][q]) << endl;
		}
	}
	
	return 0;
}

C++: #include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class ConnectNodeInfo{
	vector<vector<pair<ll,ll>>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
		graph[v].emplace_back(u,w);
	}
	void AddDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
	}
	vector<pair<ll,ll>>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

class Dijkstra{
	using Point = pair<ll,ll>;
	vector<ll> dist;
public:
	void CalcShortestPath(int start,ConnectNodeInfo& connect){
		dist.resize(connect.size(),1LL<<60);
		fill(ALL(dist),1LL<<60);
		dist[start] = 0;

		priority_queue<Point,vector<Point>,greater<Point>> Q;
		Q.emplace(0,start);
		while(!Q.empty()){
			auto p = Q.top();
			Q.pop();
			int v = p.second;
			if(dist[v]<p.first){
				continue;
			}
			for(auto e:connect[v]){
				if(dist[e.first]>dist[v]+e.second){
					dist[e.first] = dist[v]+e.second;
					Q.emplace(dist[e.first],e.first);
				}
			}
		}
	}
	ll GetDistance(int i){
		return dist[i];
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	while(true){
		int N=in(),M=in();
		if(!N && !M) break;

		ConnectNodeInfo cost_connect(M),time_connect(M);
		REP(i,N){
			int u=in()-1,v=in()-1,c=in(),t=in();
			cost_connect.AddNonDirectionalConnection(u,v,c);
			time_connect.AddNonDirectionalConnection(u,v,t);
		}
		int Q=in();
		Dijkstra DIJ;
		LOOP(Q){
			int s=in()-1,g=in()-1,r=in();
			if(!r){
				DIJ.CalcShortestPath(s,cost_connect);
				out(DIJ.GetDistance(g));
			}
			else{
				DIJ.CalcShortestPath(s,time_connect);
				out(DIJ.GetDistance(g));
			}
		}
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  int INF=2000000;
  int i,j,k,n,m,a,b,c,p,q,dp[110][110],dp1[110][110];
  while(1){
  cin >> n >> m;
    if(n==0 && m==0){
      return 0;
    }
  for(i=0;i<m;i++){
    for(j=0;j<m;j++){
      dp[i][j]=INF,dp1[i][j]=INF;
    }
  }
  for(i=0;i<n;i++){
    cin >> p >> q >> a >> b;
    p--,q--;
    dp[p][q]=a;
    dp1[p][q]=b;
    dp[q][p]=a;
    dp1[q][p]=b;
  }
  for(k=0;k<m;k++){
    for(i=0;i<m;i++){
      for(j=0;j<m;j++){
        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
        dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k][j]);
      }
    }
  }
  int d;
  cin >> d;
  for(i=0;i<d;i++){
    cin >> a >> b >> c;
    a--,b--;
    if(c==0){
      cout << dp[a][b] << endl;;
    }
    else{
      cout << dp1[a][b] << endl;
    }
  }
  }
  return 0;
}