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>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <stack>

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,b,n) for(int i=b;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

const float PI = 3.1415926;
static const int INFTY = (1<<30);

using namespace std;

typedef long long ll;
typedef long double ld;

int n, m, p, q, r;
int C[101][101], V[101][101];

void floyd() {
  rep(k,m) {
    rep(i,m) {
      if (C[i][k] == INFTY) continue;
      rep(j,m) {
        if (C[k][j] == INFTY) continue;
        C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
      }
    }
  }
  rep(k,m) {
    rep(i,m) {
      if (V[i][k] == INFTY) continue;
      rep(j,m) {
        if (V[k][j] == INFTY) continue;
        V[i][j] = min(V[i][j], V[i][k] + V[k][j]);
      }
    }
  }
}

int main() {
  while(cin >> n >> m, n) {
    rep(i, m) rep(j, m) {
      C[i][j] = INFTY;
      V[i][j] = INFTY;
    }
    
    rep(i, n) {
      int tmp_i, tmp_j, ti, co;
      cin >> tmp_i >> tmp_j >> co >> ti;
      C[tmp_i-1][tmp_j-1] = co;
      V[tmp_i-1][tmp_j-1] = ti;
    }

    floyd();

    int k;
    cin >> k;

    rep(i,k) {
      cin >> p >> q >> r;
      if(r == 0)
        cout << C[p-1][q-1] << endl;
      else
        cout << V[p-1][q-1] << endl;
    }
  }
  
  return 0;
}

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

using namespace std;
typedef pair<int,int> pii;

struct edge{
  int to;
  int cost;
  int rev;
  bitset<100> flags;
  edge(int t,int c,int r){
    to=t,cost=c,rev=r;
  }
  edge(){}
};

int dijkstra(int s,int t,int N,const vector<vector<edge> > &graph,vector<int> &clusters){
  const int INF=1<<29;
  //int target_cluster=clusters[t];
  priority_queue<pii,vector<pii>,greater<pii> > pq;
  pq.push(pii(0,s));
  vector<int> d(N,INF);
  while(pq.size()){
    pii p=pq.top();pq.pop();
    int ccost=p.first;
    int cnode=p.second;
    if(d[cnode]<ccost)continue;
    for(int i=0;i<(int)graph[cnode].size();i++){
      edge e=graph[cnode][i];
      //if(!e.flags[target_cluster])continue;
      const int ncost=e.cost+ccost;
      const int to=e.to;
      if(d[to]>ncost){
        d[to]=ncost;
        pq.push(pii(ncost,to));
      }
    }
  }
  return d[t];
}

int main(){

  int N,M;
  while(cin>>N>>M&&(N|M)){
    cerr<<N<<" "<<M<<endl;
    vector<vector<edge> > graph[2];
    for(int i=0;i<2;i++)
      for(int j=0;j<M;j++)
        graph[i].push_back(vector<edge>());
    for(int i=0;i<N;i++){
      int a,b,c,d;
      cin>>a>>b>>c>>d;
      cerr<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
      a--;b--;
      //cout<<a<<" "<<b<<endl;
      graph[0][a].push_back(edge(b,c,graph[0][b].size()));
      graph[0][b].push_back(edge(a,c,graph[0][a].size()-1));
      graph[1][a].push_back(edge(b,d,graph[1][b].size()));
      graph[1][b].push_back(edge(a,d,graph[1][a].size()-1));
    }
    vector<int> clusters(N,0);
    int K;
    cin>>K;
    cerr<<K<<endl;
    for(int q=0;q<K;q++){
      int p,q,r;
      cin>>p>>q>>r;
      cerr<<p<<" "<<q<<" "<<r<<endl;
      p--;q--;
      if(r==0){
        cout<<dijkstra(p,q,M,graph[0],clusters)<<endl;
      }
      else{
        cout<<dijkstra(p,q,M,graph[1],clusters)<<endl;
      }
    }
  }
  
  return 0;
}

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

using namespace std;
typedef pair<int,int> P;
int D[440];
int n,m,x,y,cost,Time;
vector<P> matrix1[440],matrix2[440];

void djkstra1(int s){ 
  priority_queue<P,vector<P>,greater<P> > que;
  for(int i=0;i<m+2;i++)D[i] = 10000000;
  D[s] = 0;
  que.push(P(s,0));
  while(!que.empty() ){
    P p = que.top();que.pop();
    int v = p.first;
    if(D[v] < p.second)continue;
    for(int i=0;i<matrix1[v].size();i++){
      P pp = matrix1[v][i];
      if(D[pp.first] > D[v] + pp.second){
	D[pp.first] = D[v] + pp.second;
	que.push(P(pp.first,D[pp.first]));
      }
    }
  }
}

void djkstra2(int s){ 
  priority_queue<P,vector<P>,greater<P> > que;
  for(int i=0;i<m+2;i++)D[i] = 10000000;
  D[s] = 0;
  que.push(P(s,0));

  while(!que.empty() ){
    P p = que.top();que.pop();
    int v = p.first;
    if(D[v] < p.second)continue;
    for(int i=0;i<matrix2[v].size();i++){
      P pp = matrix2[v][i];
      if(D[pp.first] > D[v] + pp.second){
	D[pp.first] = D[v] + pp.second;
	que.push(P(pp.first,D[pp.first]));
      }
    }
  }
}



int main(){
  int p,q,r;
  while(true){
    cin >> n >> m;
    if(n+m == 0)break;
   
    for(int i=0;i<=m ;i++){
      matrix1[i].clear();
      matrix2[i].clear();
    }
    for(int i=0;i<n;i++){
      cin >> x >> y >> cost >> Time;
      matrix1[x].push_back(P(y,cost));
      matrix2[x].push_back(P(y,Time));
      matrix1[y].push_back(P(x,cost));
      matrix2[y].push_back(P(x,Time));
    }  

    int k;
    cin >> k;
    for(int i=0;i<k;i++){
      cin >> p >> q >> r;
      if(r == 0){
	djkstra1(p);
	cout << D[q] << endl;
      }
      else{
	djkstra2(p);
	cout << D[q] << endl;
      }

    }

  }
  return 0;
}