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 <bits/stdc++.h>
using namespace std;
struct edge { int to, cost; };
bool operator<(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }
int n, m, a1, a2, a3, a4, q;
int main() {
	while(cin >> m >> n, n | m) {
		vector<vector<edge> > G1(n), G2(n);
		for(int i = 0; i < m; i++) {
			cin >> a1 >> a2 >> a3 >> a4; a1--, a2--;
			G1[a1].push_back(edge{a2, a3});
			G1[a2].push_back(edge{a1, a3});
			G2[a1].push_back(edge{a2, a4});
			G2[a2].push_back(edge{a1, a4});
		}
		cin >> q;
		while(q--) {
			cin >> a1 >> a2 >> a3; a1--, a2--;
			if(a3 == 0) {
				priority_queue<edge> que; que.push(edge{a1, 0});
				vector<int> d(n, 999999999); d[a1] = 0;
				while(!que.empty()) {
					int u = que.top().to; que.pop();
					for(edge e: G1[u]) {
						if(d[e.to] > d[u] + e.cost) {
							d[e.to] = d[u] + e.cost;
							que.push(edge{e.to, -d[e.to]});
						}
					}
				}
				cout << d[a2] << endl;
			}
			else {
				priority_queue<edge> que; que.push(edge{a1, 0});
				vector<int> d(n, 999999999); d[a1] = 0;
				while(!que.empty()) {
					int u = que.top().to; que.pop();
					for(edge e: G2[u]) {
						if(d[e.to] > d[u] + e.cost) {
							d[e.to] = d[u] + e.cost;
							que.push(edge{e.to, -d[e.to]});
						}
					}
				}
				cout << d[a2] << endl;
			}
		}
	}
}

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

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

int N,M,K;
const int MAXN=128;
const int INF=1e9;
int G[2][MAXN][MAXN];

int dk(int from,int to,int type)
{
	bool ok[MAXN];
	int cost[MAXN];
	memset(ok,0,sizeof(ok));
	memset(cost,0,sizeof(cost));
	ok[from]=true;

	while(!ok[to])
	{
		int t,v=INF; 
		rep(i,M) if(ok[i]) rep(j,M) if(!ok[j]&&G[type][i][j])
		{
			if(cost[i]+G[type][i][j]<v){ v=cost[i]+G[type][i][j]; t=j; }
		}

		if(v==INF){ cout<<"ERROR"<<endl; break; } else { cost[t]=v; ok[t]=true; }
	}

	return cost[to];
}

int main()
{
	while(cin>>N>>M&&(N||M))
	{
		int a,b,c,d;

		rep(i,N)
		{ 
			cin>>a>>b>>c>>d; --a; --b;
			G[0][a][b]=G[0][b][a]=c;
			G[1][a][b]=G[1][b][a]=d;
		}

		cin>>K;
		rep(i,K)
		{
			cin>>a>>b>>c; --a; --b;
			cout<<dk(a,b,c)<<endl;
		}
	}

	return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>
#define INF (int)1e9


int common_part(int m, int p, int q, std::vector<std::vector<std::pair<int, int> > > v); 
void dijkstra(int m, int p, std::vector<std::vector<std::pair<int, int> > > &v, std::vector<int> &rvec); 


int main(void) {
    int n;
    int m;

    int a;
    int b;
    int cost;
    int time;

    int k;

    int p;
    int q;
    int r;

    int res;

    while (true) {
        std::cin >> n >> m;
        if (n == 0 && m == 0) {
            break; 
        }

        std::vector<std::vector<std::pair<int, int> > > vcost(m);
        std::vector<std::vector<std::pair<int, int> > > vtime(m);

        for (int i = 0; i < n; i++) {
            std::cin >> a >> b >> cost >> time;
            --a;
            --b;
            vcost[a].push_back(std::make_pair(cost, b));
            vcost[b].push_back(std::make_pair(cost, a));
            vtime[a].push_back(std::make_pair(time, b));
            vtime[b].push_back(std::make_pair(time, a));
        }

        std::cin >> k;

        for (int i = 0; i < k; i++) {
            std::cin >> p >> q >> r;
            --p;
            --q;

            // Bellman Ford or Dijkstra
            if (r == 0) {
                res = common_part(m, p, q, vcost);
            } else {
                res = common_part(m, p, q, vtime);
            }
            std::cout << res << std::endl;
        }
    }
    return 0;
}

void dijkstra(int m, int p, std::vector<std::vector<std::pair<int, int> > > &v, std::vector<int> &rvec) {
    std::priority_queue<std::pair<int, int> > pq;
    std::vector<int> search_count(m, 0);
    int start_value;
    int start_target;
    int end_value;
    int end_target;
    pq.push(std::make_pair(rvec[p] * (-1), p));

    while(true) {
        if (pq.empty() == 1) {
           break; 
        }
        start_value = pq.top().first * (-1); 
        start_target = pq.top().second;
        pq.pop();
        if (search_count[start_target] == 0) {
            ++search_count[start_target];
            for (int i = 0; i < v[start_target].size(); i++) {
                end_value = v[start_target][i].first;
                end_target = v[start_target][i].second;
                if (rvec[end_target] > end_value + rvec[start_target]) {
                    rvec[end_target] = end_value + rvec[start_target];
                }
                pq.push(std::make_pair(rvec[end_target] * (-1), end_target));
            }
        }
    }

    return;
} 

int common_part(int m, int p, int q, std::vector<std::vector<std::pair<int, int> > > v) {
    std::vector<int> rvec(m, INF);
    rvec[p] = 0;

    //bellman_ford(m, v, rvec);
    dijkstra(m, p,  v, rvec);

    return rvec[q];
}