INF = 2 << 32

Enumerator.new {|y|
  until (n_m = gets.split(" ").map(&:to_i)) == [0, 0]
    n, m = *n_m
    lines = n.times.map { gets.split(" ").map(&:to_i) }
    issues = gets.to_i.times.map { gets.split(" ").map(&:to_i) }
    y << [m, lines, issues]
  end
}
  .flat_map {|(m, lines, issues)|
    # init
    dic = []
    [0, 1].each {|t|
      dic[t] = []
      (1..m).each {|i| 
        dic[t][i] = []
        (1..m).each {|j|
          dic[t][i][j] = INF
        }
        dic[t][i][i] = 0
      }
    }

    # load
    lines.each {|(a, b, c_0, c_1)|
      dic[0][a][b] = c_0
      dic[0][a][b] = c_0
      dic[1][a][b] = c_1
      dic[1][a][b] = c_1
    }

    # calc
    [0, 1].each {|t|
      (1..m).each {|i| 
        (1..m).each {|j|
          (1..m).each {|k|
            dic[t][i][j] = [dic[t][i][j], dic[t][i][k] + dic[t][k][j]].min
          }
        }
      }
    }

    issues.map {|start, goal, cost_type|
      # fetch
      dic[cost_type][start][goal]
    }
  }
  .each(&method(:puts))