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 <cstdio>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <functional>
#include <utility>

using namespace std;

class Station {
public:
  int to;
  int cost;
  int time;
  Station(){
	to = cost = time = 0;
  }
  Station( const int to, const int cost, const int time ){
	this->to = to;
	this->cost = cost;
	this->time = time;
  }
};

class mycmp
{
public:
  bool operator() ( pair<int, int>& lhs, pair<int, int>& rhs )
  {
	return lhs.second > rhs.second;
  }
};

const int COST = 0;
const int TIME = 1;

int solve( const int p, const int q, const int r,
		   const vector<vector<Station> > table ) {

  priority_queue<pair<int, int>, vector<pair<int, int> >, mycmp > que;
  que.push( make_pair( p, 0 ) );

  set<int> visited;
  
  while ( !que.empty() ) {
  	auto elem = que.top();
  	const int stat = elem.first;
  	const int cost = elem.second;
  	que.pop();
	
  	if ( stat == q ) {
  	  return cost;
  	} else if ( visited.find( stat ) == visited.end() ) {
  	  visited.insert( stat );
  	  for ( const Station s : table[stat] ) {
  		if ( r == COST ) {
  		  que.push( make_pair( s.to, cost + s.cost ) );
  		} else {
  		  que.push( make_pair( s.to, cost + s.time ) );
  		}
  	  }
  	}	
  }
  return -1;
}
  
int main() {
  
  while ( true ) {
   	int n, m;
   	cin >> n >> m;
   	if ( n == 0 && m == 0 ) break;
	vector<vector<Station> > table(m + 1);
	for ( int i = 0; i < n; i++ ) {
	  int from, to, cost, time;
	  cin >> from >> to >> cost >> time;
	  table[ from ].push_back( Station( to, cost, time ) );
	  table[ to ].push_back( Station( from, cost, time ) );
	}
	int k;
	cin >> k;
	for ( int i = 0; i < k; i++ ) {
	  int p, q, r;
	  cin >> p >> q >> r;
	  cout << solve( p, q, r, table ) << endl;
	}
  }  
}

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

using namespace std;

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

class L{
	public:
	int a,c,t;
	L(int a,int c,int t):a(a),c(c),t(t){}
};

class S{
	public:
	int now;
	int p;
	S(int now,int p):now(now),p(p){}
	bool operator<(const S&a)const{
		return p>a.p;
	}
};

int main(){
	
	while(1){
		int n,m;
		cin>>n>>m;
		
		if(n==0)break;
		
		vector<L> load[111];
		
		rep(i,n){
			int a,b,c,t;
			cin>>a>>b>>c>>t;
			
			load[a].push_back(L(b,c,t));
			load[b].push_back(L(a,c,t));
		}
		
		
		int k;
		cin>>k;
		
		rep(pp,k){
			int aa,bb,cc;
			cin>>aa>>bb>>cc;
			
			priority_queue<S> que;
			que.push(S(1,0));
			
			int visit[111]={0};
			while(1){
				if(que.empty())break;
				
				S u = que.top();
				que.pop();
				
				//printf("%d %d\n",u.now,u.p);
				
				if(u.now==m){
					printf("%d\n",u.p);
					break;
				}
				
				if(visit[u.now]==1)continue;
				visit[u.now]=1;
				
				rep(i,load[u.now].size()){
					
					L e = load[u.now][i];
					
					if(cc==0){
						que.push(S(e.a, u.p+e.c));
					}else{
						que.push(S(e.a, u.p+e.t));
					}
				}
			}
		}
	}
}

C++: #include<cmath>
#include<cctype>
#include<cstdlib>
#include<cstdio>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<utility>
#include<queue>

using namespace std;
int n,m;
const int MAXN = 1000;
int t[MAXN][MAXN];
int c[MAXN][MAXN];

void solve(){
  for(int k = 0;k < n; ++k){
    for(int i = 0;i < n; ++i){
      for(int j = 0;j < n; ++j){
	t[i][j] = min(t[i][j],t[i][k] + t[k][j]);
	c[i][j] = min(c[i][j],c[i][k] + c[k][j]);
      }
    }
  }
}
const int INF = INT_MAX/3;
void init(){
  for(int i = 0;i < n; ++i){
    for(int j = 0;j < n;j++){
      c[i][j] = t[i][j] = INF;
    }
  }
  for(int i = 0;i < n;i++){
    c[i][i] = t[i][i] = 0;
  }
}


int main(){
  ios::sync_with_stdio(false);

  while(cin >> n >> m && n+m > 0){
    init();
    int a,b,icost,itime;
    for(int i = 0;i < n;i++){
      cin >> a >> b >> icost >> itime;
      t[a][b] = t[b][a] = itime;
      c[a][b] = c[b][a] = icost;
    }
    solve();
    int k;
    cin >> k;
    for(int i = 0;i < k; ++i){
      int p,q,r;
      cin >> p >> q >> r;
      if(r == 1){
	cout << t[p][q] << endl;
      }else{
	cout << c[p][q] << endl;
      }
    }
  }
  return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int main(){
  const int MAX = 1e5;
  for(int n,m;cin>>n>>m,n;){
    int cost[m][m];
    int time[m][m];
    for(int i=0;i<m;i++){
      for(int j=0;j<m;j++){
	cost[i][j] = MAX;
	time[i][j] = MAX;
      }
    }
    int a,b,c,t;
    for(int i=0;i<n;i++){
      cin>>a>>b>>c>>t;
      cost[max(a-1,b-1)][min(a-1,b-1)] = c;
      time[max(a-1,b-1)][min(a-1,b-1)] = t;
    }
    for(int k=0;k<m;k++){
      for(int i=0;i<m;i++){
	for(int j=0;j<=i;j++){
	  int mai = max(i,k),mii=min(i,k);
	  int maj = max(j,k),mij=min(j,k);
	  if(cost[i][j]>cost[mai][mii]+cost[maj][mij])
	    cost[i][j] = cost[mai][mii]+cost[maj][mij];
	  if(time[i][j]>time[mai][mii]+time[maj][mij])
	    time[i][j] = time[mai][mii]+time[maj][mij];
	}
      }
    }
    int l,r;
    cin>>l;
    for(int i=0;i<l;i++){
      cin>>a>>b>>r;
      if(r)
	cout<<time[max(a-1,b-1)][min(a-1,b-1)]<<endl;
      else
	cout<<cost[max(a-1,b-1)][min(a-1,b-1)]<<endl;      
    }
  }
  return 0;
}