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<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

int c[100][100]={};
int t[100][100]={};

int main()
{
  int n,m,a,b;
  int i,j,k;
  int p,q,r;

  while(1){
    cin>>n>>m;
    if(n==0 && m==0)break;

    rep(i,m+1)rep(j,m+1)c[i][j]=t[i][j]=INF;//INFテ」ツ?ァテ・ツ按敕ヲツ慊淌・ツ個?
    rep(i,m+1)c[i][i]=t[i][i]=0;//テ・ツ青古ゥツァツ?」ツ?ッ0

    rep(i,n){
      cin>>a>>b;
      cin>>c[a][b]>>t[a][b];
      c[b][a]=c[a][b];
      t[b][a]=t[a][b];
    }
    
    rep(k,m+1)rep(i,m+1)rep(j,m+1){
      c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
      t[i][j]=min(t[i][j],t[i][k]+t[k][j]);
    }

    cin>>k;
    rep(i,k){
      cin>>p>>q>>r;
      if(r)
	cout<<t[p][q]<<endl;
      else
	cout<<c[p][q]<<endl;
    }
  }
}

C++: #include<iostream>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define INF 30000

struct E
{
    int a,b,c,t;
    E(){};
    E(int a,int b,int c,int t):a(a),b(b),c(c),t(t){};
};
E cs[1000];
unsigned int d[310];

int main()
{
    int n,m,k,p,q,r;
    while(cin >> n >> m)
    {
        if(n==0 && m==0)break;
        
        int ta,tb,tc,tt;
        for(int i=0;i<2*n;i+=2)
        {
            cin >> ta>>tb>>tc >>tt;
            cs[i].a = ta;cs[i].b = tb;cs[i].c = tc;cs[i].t = tt;
            cs[i+1].a = tb;cs[i+1].b = ta;cs[i+1].c = tc;cs[i+1].t = tt;
            //cs[i] = E(ta,tb,tc,tt);
            //cs[i+1] = E(tb,ta,tc,tt);
        }

        cin >> k;
        rep(i,k)
        {
            memset(d,INF,sizeof(d));
            cin >> p >> q >>r;
            d[p] = 0;

            int update = 0;
            if(r==0)while(true)
            {
                update = 0;
                rep(j,n*2)
                {
                   if(d[cs[j].a] != INF && d[cs[j].b] > d[cs[j].a] + cs[j].c)
                   {
                       update = 1;
                       d[cs[j].b] =  d[cs[j].a] + cs[j].c;
                   }
                }
                if(!update) break;
            }
            if(r==1)while(true)
            {
                update = 0;
                rep(j,n*2)
                {
                   if(d[cs[j].a] != INF && d[cs[j].b] > d[cs[j].a] + cs[j].t)
                   {
                       update = 1;
                       d[cs[j].b] =  d[cs[j].a] + cs[j].t;
                   }
                }
                if(!update) break;
            }
            cout << d[q] << endl;
        }
        
    }

    return 0;
}

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

#define INF (1<<29)

int main(){
  int time[101][101], cost[101][101];
  
  int n, m;
  int from, to, Cost, Time;
  while(cin >> n >> m){
    if(n == 0 && m == 0) break;
    for(int i = 0 ; i <= m ; i++){
      for(int j = 0 ; j <= m ; j++){
	if(i == j) time[i][j] = cost[i][j] = 0;
	else time[i][j] = cost[i][j] = INF;
      }
    }
    
    while(n--){
      cin >> from >> to >> Cost >> Time;
      cost[from][to] = Cost;
      time[from][to] = Time;
    }
    
    for(int k = 1 ; k <= m ; k++){
      for(int i = 1 ; i <= m ; i++){
	for(int j = 1 ; j <= m ; j++){
	  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]);
	}
      }
    }
    int num;
    cin >> n;
    while(n--){
      cin >> from >> to >> num;
      if(num == 0) cout << cost[from][to] << endl;
      else cout << time[from][to] << endl;
    }
  }
  return 0;
}

C++: #include<stack>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
static const int INFTY = (1 << 21);
int main(){
	int n, m, a, b, cost, time;
	int kk, p, q, r;
	int sta_c[101][101];
	int sta_t[101][101];
	while (cin >> n >> m, n, m){
		for (int i = 0; i < 101; i++){
			for (int j = 0; j < 101; j++){
				sta_c[i][j] = sta_t[i][j] = INFTY;
			}
		}
		for (int i = 0; i < n; i++){
			cin >> a >> b >> cost >> time;
			sta_c[a][b] = cost; sta_c[b][a] = cost;
			sta_t[a][b] = time; sta_t[b][a] = time;
		}
		for (int k = 1; k <= m; k++){
			for (int i = 1; i <= m; i++){
				if (sta_c[i][k] == INFTY) continue;
				for (int j = 1; j <= m; j++){
					if (sta_c[k][j] == INFTY) continue;
					sta_c[i][j] = min(sta_c[i][j], sta_c[i][k] + sta_c[k][j]);
					sta_t[i][j] = min(sta_t[i][j], sta_t[i][k] + sta_t[k][j]);
				}
			}
		}
		cin >> kk;
		for (int i = 0; i < kk; i++){
			cin >> p >> q >> r;
			if (r == 0) cout << sta_c[p][q] << endl;
			else cout << sta_t[p][q] << endl;
		}
	}
	return 0;
}