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 = newSeq[seq[(int, int)]](n)

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

dp[0].add (0, 0)

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

let
  times = newSeq.collect:
            for (_, a) in dp[n-1]: a

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