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]
					t_newlen := t_dist[i][k] + t_dist[k][j]
					if c_newlen < c_dist[i][j] {
						c_dist[i][j] = c_newlen
						c_prev[i][j] = c_prev[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 <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
*/

int main(){
    ll N,M;
    while(true){
        cin >> N >> M;
        if(N == 0 && M == 0)break;
        vector<vector<ll>> cost(M + 1,vector<ll>(M + 1,INF));
        vector<vector<ll>> time(M + 1,vector<ll>(M + 1,INF));
        ll p,q,c,t;
        rep(i,N){
            cin >> p >> q >> c >> t;
            cost[p][q] = c;
            cost[q][p] = c;
            time[p][q] = t;
            time[q][p] = t;
        }
        rep(k,M + 1){
            rep(i,M + 1){
                rep(j,M + 1){
                    cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j]);
                    time[i][j] = min(time[i][j],time[i][k] + time[k][j]);
                }
            }
        }
        ll K;
        cin >> K;
        vector<ll> fr(K);
        vector<ll> to(K);
        vector<ll> ti(K);
        rep(i,K)cin >> fr[i] >> to[i] >> ti[i];
        rep(i,K){
            if(ti[i] == 1){
                cout << time[fr[i]][to[i]] << "\n";
            }
            else{
                cout << cost[fr[i]][to[i]] << "\n";
            }
        }
    }
}

C++: #include <stdio.h>
#include <vector>

using namespace std;

class Edge{
public:
	int from,to,cost,time;
	void swap(){
		int self = from;
		from = to;
		to = self;
	}
	int getvalue(int r){
		if(r == 0){
			return cost;
		}else{
			return time;
		}
	}
};

vector<Edge> edge;
int n,m;

int solve(const int p,const int q,const int r);

int main(){
	edge.clear();
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		Edge ed;
		scanf("%d %d %d %d",&ed.from,&ed.to,&ed.cost,&ed.time);
		edge.push_back(ed);
		ed.swap();
		edge.push_back(ed);
	}
	
	int k;
	scanf("%d",&k);
	for(int i=0;i<k;i++){
		int p,q,r;
		scanf("%d %d",&p,&q);
		if(p==0 && q==0){
			return 0;
		}
		scanf("%d",&r);
		printf("%d\n",solve(p,q,r));
	}
}

int solve(const int p,const int q,const int r){
	const int INF = 2147483647;
	int *a = new int[m+1];
	for(int i=0;i<=m;i++){
		a[i] = INF;
	}
	a[p] = 0;
	bool update;
	while(true){
		update = false;
		vector<Edge>::iterator it = edge.begin();
		while(it != edge.end()){
			if(a[(*it).from] != INF && a[(*it).to] > a[(*it).from] + (*it).getvalue(r)){
				a[(*it).to] = a[(*it).from] + (*it).getvalue(r);
				update = true;
			}
			it++;
		}
		if(!update){
			break;
		}
	}
	
	int ans = a[q];
	return a[q];
}

C++: #include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <iterator>
#define INF 100000100
using namespace std;


int minimize(int start, int goal, map<int,int>* mp,int n);


int main(void){
  int n,m;
  while(true){
    cin>>n>>m;
    if(n==0 and m==0){break;}
    map<int,int> costs[n];
    map<int,int> times[n];
    int a,b,c,t;
    for(int i=0;i<n;i++){
      cin>>a>>b>>c>>t;
      a--;
      b--;
      costs[a][b]=c;
      costs[b][a]=c;
      times[a][b]=t;
      times[b][a]=t;
    }
    int k;
    cin>>k;
    int p,q,r;
    for(int i=0;i<k;i++){
      cin>>p>>q>>r;
      p--;
      q--;
      if(r==0){
        cout<<minimize(p,q,costs,n)<<endl;
      }
      else{
        cout<<minimize(p,q,times,n)<<endl;
      }
    }
  }
  return 0;
}

int minimize(int start, int goal, map<int,int>* mp,int n){
  int d[n];
  for(int i=0;i<n;i++){
    d[i]=INF;
  }
  d[start]=0;
  vector<int> next,_next;
  next.push_back(start);
  while(next.size()>0){
    _next.clear();
    for(auto iter=next.begin();iter!=next.end();iter++){
      int s=*iter;
      for(auto iter2=mp[s].begin();iter2!=mp[s].end();iter2++){
        int key=iter2->first;
        int value=iter2->second;
        if(d[key]>d[s]+value){
          d[key]=d[s]+value;
          _next.push_back(key);
        }
      }
    }
    next.clear();
    copy(_next.begin(),_next.end(),back_inserter(next));
  }
  return d[goal];
}