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])
			}
		}
	}
}

Python: max_ = 1000000
#def solv(p,q):
    #global costs
    #global times
    #global stack
    #if times[p][q] < max_:
        ##最短経路算出済み
        #return costs[p][q],times[p][q]
#
    #if p == q:
        #return 0,0
#
    #min_cost = max_
    #min_time = max_
    #stack.append(p)
#
    #for s in senro :
        #if (s[0] == p or s[1] == p) :
            #next_ = s[1] if s[0]==p else s[0]
            #if next_ in stack: #経過済みは無視
                #continue
#
            #c,t = solv(next_,q)
            #min_cost = min(c + s[2],min_cost)
            #min_time = min(t + s[3],min_time)
    #
    #costs[p][q] = min_cost
    #times[p][q] = min_time
#
    #stack.pop()
#
    #return min_cost,min_time

while True:
    n,m = list(map(int,input().split()))
    if n == 0 and m == 0:
        break

    costs = [[max_ for i in range(m+1)] for j in range(m+1)]
    times = [[max_ for i in range(m+1)] for j in range(m+1)]

    #senro = [list(map(int,input().split())) for i in range(n)]
    for i in range(n):
        s = list(map(int,input().split()))
        costs[s[0]][s[1]] = s[2]
        costs[s[1]][s[0]] = s[2]
        times[s[0]][s[1]] = s[3]
        times[s[1]][s[0]] = s[3]

    for i in range(1,m+1):
        for k in range(1,m+1):
            for j in range(1,m+1):
                costs[i][j] = min(costs[i][j],costs[i][k] + costs[k][j])
                times[i][j] = min(times[i][j],times[i][k] + times[k][j])

    k = int(input())
    for i in range(k):
        p,q,r = list(map(int,input().split()))
        print(times[p][q] if r==1 else costs[p][q])

Python: ### Warshall???Floyd ###

INF = float("inf")

#????????°V??§?????????: ??°??????????????????????????¢???INF?????????????????????????????¢???0
def init(V):
    d = [[INF] * V for i in range(V)]
    for i in range(V):
        d[i][i] = 0
    
    return d

#????????????????¨????
def wf(d, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

#for print debug
def print_matrix(m):
    for row in m:
        print('\t'.join(map(str, row)))

while True:
    #V:???????????°(m)??? E:????????°(n)
    E, V = map(int, input().split())
    
    if E == V == 0:
        break
    
    #?????????
    money = init(V)
    time = init(V)
    
    #??°??????????????? 
    for i in range(E):
        u, v, c, t = map(int, input().split())
        u -= 1; v -= 1;
        money[u][v] = money[v][u] = c
        time[u][v] = time[v][u] = t
    
    #????????????????¨????
    wf(money, V)
    wf(time, V)
    
    #?????????????????°
    K = int(input())
    
    #??????????????????????§£???
    for i in range(K):
        p, q, r = map(int, input().split())
        p -= 1; q -= 1
        if r == 0:
            print(money[p][q])
        else:
            print(time[p][q])

Python: from heapq import heappop as hpop
from heapq import heappush as hpush

def main():
  
  while True:
    n, m = map(int, input().split())
    
    if not n:
      break
    
    cost_edges = [[] for _ in range(m)]
    time_edges = [[] for _ in range(m)]
  
    for _ in range(n):
      a, b, c, t = map(int, input().split())
      cost_edges[a - 1].append((c, b - 1))
      cost_edges[b - 1].append((c, a - 1))
      time_edges[a - 1].append((t, b - 1))
      time_edges[b - 1].append((t, a - 1))
    
    k = int(input())
  
    for _ in range(k):
      start, goal, r = map(int ,input().split())
      start -= 1
      goal -= 1
      
      if r:
        edges = time_edges
      else:
        edges = cost_edges
  
      que = [(0, start)]
      visited = [False for _ in range(m)]
      
      while que:
        score, station = hpop(que)
        visited[station] = True
        
        if station == goal:
          print(score)
          break
  
        for c, to_station in edges[station]:
          if not visited[to_station]:
            hpush(que, (score + c, to_station))

main()

Python: import sys
f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    dist = [[(float('inf'),float('inf'))  for j in range(m)] for i in range(m)]    
    for ai, bi, cost, time in abct:
        dist[ai - 1][bi - 1] = (cost, time)
    for k in range(m):
        for i in range(m):
            for j in range(m):
                if dist[i][j][0] > dist[i][k][0] + dist[k][j][0]:
                    dist[i][j] = (dist[i][k][0] + dist[k][j][0], dist[i][j][1])
                if dist[i][j][1] > dist[i][k][1] + dist[k][j][1]:
                    dist[i][j] = (dist[i][j][0], dist[i][k][1] + dist[k][j][1])
        
    k = int(f.readline())
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        print(dist[p - 1][q - 1][r])