import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.io.StdIn._
object Main extends App {

  val Array(v, e, f) = readLine.trim.split(' ').map(_.toInt)
  val nodes = Array.fill(v){ArrayBuffer[Edge]()}
  for (_ ← 0 until e) {
    val Array(u, v, c, d) = readLine.trim.split(' ').map(_.toInt)
    nodes(u).append(Edge(v, c, d))
    nodes(v).append(Edge(u, 0, -d))
    nodes(u).last.pair = nodes(v).last
    nodes(v).last.pair = nodes(u).last
  }
  val potential = Array.fill(v){0L}
  val minCost = Array.fill(v){Long.MaxValue}
  val prev = Array.fill(v){nodes.head.head}
  val queue = mutable.PriorityQueue[(Int, Long)]()(Ordering.by[(Int, Long), Long](_._2).reverse)
  var flow = 0
  var wholeCost = 0L
  var hasFlow = true
  while(hasFlow && flow < f) {
    hasFlow = false
    minCost.indices.foreach(i ⇒ minCost(i) = Long.MaxValue)
    queue.enqueue((0, 0L))
    minCost(0) = 0L
    while (queue.nonEmpty) {
      val (current, cost) = queue.dequeue()
      if (current != v - 1 && minCost(current) == cost) {
        for (e@Edge(next, flow, distance) ← nodes(current) if flow > 0) {
          if (minCost(next) > potential(current) - potential(next) + distance + cost) {
            minCost(next) = potential(current) - potential(next) + distance + cost
            prev(next) = e
            queue.enqueue((next, minCost(next)))
          }
        }
      }
    }
    hasFlow = minCost(v - 1) != Long.MaxValue
    if (hasFlow) {
      for (i ← 0 until v) potential(i) += minCost(i)
      var minFlow = Int.MaxValue
      var last = v - 1
      while (last != 0) {
        minFlow = math.min(minFlow, prev(last).flow)
        last = prev(last).pair.to
      }
      val addFlow = math.min(f - flow, minFlow)
      wholeCost += addFlow * potential(v - 1)
      flow += addFlow
      last = v - 1
      while (last != 0){
        prev(last).flow -= addFlow
        prev(last).pair.flow += addFlow
        last = prev(last).pair.to
      }
    }
  }
  println(if (flow == f) wholeCost else -1)
  case class Edge(to: Int, var flow: Int, cost: Int) {
    private var mPair: Option[Edge] = None
    def pair: Edge = mPair.get
    def pair_=(edge: Edge): Unit = mPair = Some(edge)
  }
}
