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 <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;

void dijkstra(int from, int mode);

pair<int, int> route[1000][1000];
int mini[1000];
int n, m;
int k;

int main()
{
	while (scanf("%d %d", &n, &m) * n != 0){
		for (int i = 0; i < n; i++){
			int a, b;
			int cost, time;
			
			scanf("%d %d %d %d", &a, &b, &cost, &time);
			a--, b--;
			route[a][b] = make_pair(cost, time);
			route[b][a] = make_pair(cost, time);
		}
		
		scanf("%d", &k);
		while (k-- > 0){
			fill(mini, mini + m, 100000000);
			int p, q, r;
			scanf("%d %d %d", &p, &q, &r);
			p--, q--;
			mini[p] = 0;
			dijkstra(p, r);
			printf("%d\n", mini[q]);
		}
	}
	
	return 0;
}

void dijkstra(int from, int mode)
{
	queue<int> to;
	
	for (int i = 0; i < m; i++){
		if (route[from][i].first + route[from][i].second == 0){
			continue;
		}
		if (mode == 0 && mini[i] > mini[from] + route[from][i].first){
			mini[i] = mini[from] + route[from][i].first;
			to.push(i);
		}
		else if (mode == 1 && mini[i] > mini[from] + route[from][i].second){
			mini[i] = mini[from] + route[from][i].second;
			to.push(i);
		}
		if (k == 0){
			route[from][i] = make_pair(0, 0);
		}
	}
	while (!to.empty()){
		dijkstra(to.front(), mode);
		to.pop();
	}
}

C++: #include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n) 

int main(void){  
  int cost[100][100]={0};
  int time[100][100]={0};
  int n,m,a,b,c,t,h,p,q,r;
  cin >> n >> m;
  REP(i,n){
    cin >> a >> b >> c >> t;
    cost[a-1][b-1] = cost[b-1][a-1] = c;
    time[a-1][b-1] = time[b-1][a-1] = t;
  }
  REP(i,m)
    REP(j,m){
      if(!cost[i][j]) cost[i][j] = 10000000;
      if(!time[i][j]) time[i][j] = 10000000;
    }
  REP(k,m)
    REP(i,m)
      REP(j,m){
        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]);
      }
  cin >> h;
  REP(i,h){
    cin >> p >> q >> r;
    if(r==0) cout << cost[p-1][q-1] << endl;
    else cout << time[p-1][q-1] << endl;
  }
  return 0;
}

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

#define INF 1<<29

using namespace std;

int n;
int c[101][101];
int t[101][101];
int flg;

int washa(int st,int en,int va){
	if(flg==1){
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(c[i][j]>c[k][i]+c[j][k]){
						c[i][j]=c[k][i]+c[j][k];
					}
					if(t[i][j]>t[k][i]+t[j][k]){
						t[i][j]=t[k][i]+t[j][k];
					}
				}
			}
		}
		flg=0;
	}
	if(va==0){
		return c[st][en];
	}else{
		return t[st][en];
	}
}

int main(){
	int m;
	for(int i=0;i<101;i++){
		for(int j=0;j<101;j++){
			c[i][j]=t[i][j]=INF;
		}
	}
	flg=1;
	
	scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++){
		int a,z,s,x;
		scanf("%d%d%d%d",&a,&z,&s,&x);
		c[a][z]=c[z][a]=s;
		t[a][z]=t[z][a]=x;
	}
	
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int a,z,s;
		scanf("%d%d%d",&a,&z,&s);
		
		printf("%d\n",washa(a,z,s));
	}
}

C++: #include<iostream>
#include<vector>
#include<map>
#include<climits>
using namespace std;

#define NONE INT_MAX

int n,m,k,a,b,c,d,p,q,r;
vector< vector<int> >M,N;

int Dijkstra(int start,int goal)
{
  vector<int>d(n,NONE),visited(n,0);
  multimap<int,int>q;

  d[start]=0;
  q.insert(make_pair(0,start));

  while(q.size()){
    int u,v;
    u=q.begin()->second;
    q.erase(q.begin());
    if(visited[u]==true)continue;
    visited[u]=true;
    for(v=0;v<n;v++){
      if(M[u][v]==NONE)continue;
      if(visited[v]==true)continue;
      if(d[v]<=d[u]+M[u][v])continue;
      d[v]=d[u]+M[u][v];
      q.insert(make_pair(d[v],v));
    }
  }
  return d[goal];
}

int Dijkstra2(int start,int goal)
{
  vector<int>d(n,NONE),visited(n,0);
  multimap<int,int>q;

  d[start]=0;
  q.insert(make_pair(0,start));

  while(q.size()){
    int u,v;
    u=q.begin()->second;
    q.erase(q.begin());
    if(visited[u]==true)continue;
    visited[u]=true;
    for(v=0;v<n;v++){
      if(N[u][v]==NONE)continue;
      if(visited[v]==true)continue;
      if(d[v]<=d[u]+N[u][v])continue;
      d[v]=d[u]+N[u][v];
      q.insert(make_pair(d[v],v));
    }
  }
  return d[goal];
}

int main()
{
  while(cin>>m>>n,m|n){
    M.resize(n);
    N.resize(n);
    for(int i=0;i<n;i++){
      M[i].resize(n,NONE);
      N[i].resize(n,NONE);
    }
    for(int i=0;i<m;i++){
      cin>>a>>b>>c>>d;
      a--;b--;
      M[a][b]=c;
      M[b][a]=c;
      N[a][b]=d;
      N[b][a]=d;
    }
    cin>>k;
    for(int i=0;i<k;i++){
      cin>>p>>q>>r;
      p--;q--;
      if(r==0)cout<<Dijkstra(p,q)<<endl;
      else cout<<Dijkstra2(p,q)<<endl;
    }
  }
}