INF = 1.0 / 0.0

def used_edges(sink, pre_node)
  ans = []
  p = pre_node[sink]
  while p != nil
    v, i = p
    ans << $edges[v][i]
    p = pre_node[v]
  end
  return ans
end

def min_cost_flow(source, sink, required_flow)
  res = 0
  while required_flow > 0
    dist = Array.new($n){INF}
    dist[source] = 0
    pre_node = Array.new($n){nil}

    loop do
      updated = false
      $n.times{|v|
        next if dist[v] == INF
        $edges[v].each_with_index{|edge, i|
          capacity, target, cost = edge[0..2]
          new_dist = dist[v] + cost
          if capacity > 0 &&  dist[target] > new_dist
            dist[target] = new_dist
            pre_node[target] = [v, i]
            updated = true
          end
        }
      }
      break if not updated
    end
    return -1 if dist[sink] == INF

    path = used_edges(sink, pre_node)
    aug = required_flow
    path.each{|e|
      aug = e[0] if aug > e[0]
    }

    required_flow -= aug

    res += aug * dist[sink]
    path.each{|e|
      target,idx = e[1], e[3]
      e[0] -= aug
      $edges[target][idx][0] += aug
    }
  end
  return res
end

$n, m, f = gets.split.map(&:to_i)
$edges = Array.new($n){[]}

m.times{|i|
  s, t, c, d = gets.split.map(&:to_i)
  ls = $edges[s].size
  lt = $edges[t].size
  $edges[s] << [c, t, d, lt]
  $edges[t] << [0, s,-d, ls]
}

puts min_cost_flow(0, $n-1, f)