import sequtils, strutils, sugar

let
  # 街の数、持ち金、道の数
  n, c, v = parseInt stdin.readLine
  # 発、着、費用、時間
  s, t, y, m = stdin.readLine.split.map parseInt

var
  # (行き先、費用、時間)
  g = newSeq[seq[(int, int, int)]](n)
  # [合計費用](合計時間)
  dp = newSeqWith(n, (-1).repeat c+1)

for i in 0 .. v-1:
  g[s[i]-1].add (t[i]-1, y[i], m[i])

dp[0][0] = 0

for i in 0 ..< n-1:
  for j in 0 .. c:
    let
      timeX = dp[i][j]
    if timeX == -1: continue
    for (node, yenY, timeY) in g[i]:
      let
        yen = j + yenY
        time = timeX + timeY
      if yen > c: continue
      let
        next = dp[node][yen]
      if next != -1 and next <= time: continue
      dp[node][yen] = time

let
  times = newSeq.collect:
            for a in dp[n-1]:
              if a != -1: a

echo:
  if times.len == 0: -1
  else: min times