INF = 2 << 32

class CostDic
  def initialize m
    @m = m
    @a = Array.new(2 * (m ** 2), INF)
    [0, 1].each {|t|
      (1..m).each {|i|
        put t, i, i, 0
      }
    }
  end

  def put type, start, goal, cost
    @a[ref_of type, start, goal] = cost
  end

  def get type, start, goal
    @a[ref_of type, start, goal]
  end

  def ref_of type, start, goal
    (goal - 1) + (start - 1) * @m + type * (@m ** 2)
  end
end

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)|
    dic = CostDic.new(m)

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

    # calc
    [0, 1].each {|t|
      (1..m).each {|i|
        ((i + 1)..m).each {|j|
          (1..m).each {|k|
            alt = dic.get(t, i, k) + dic.get(t, k, j)
            if dic.get(t, i, j) > alt
              dic.put(t, i, j, alt)
              dic.put(t, j, i, alt)
            end
          }
        }
      }
    }

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