class PQueue
  attr_accessor :node
  def initialize
    @node = []
  end
  def insert(num)
    i = @node.size
    @node[i] = num
    down_heap(i)
  end
  def extract
    ret = @node[0]
    if @node.size > 1
      @node[0] = @node.pop()
      up_heap(0)
    else
      @node = []
    end
    return ret
  end
  def delete(node)
    i = @node.index(node)
    if i == @node.size - 1
      @node.pop
    else
      @node[i] = @node.pop
      copy = @node.clone
      down_heap(i)
      if copy == @node
        up_heap(i)
      end
    end
  end
  def modify(old, new)
    delete(old)
    insert(new)
  end
  def up_heap(i)
    h = @node.size
    largest = i
    l = 2 * i + 1
    largest = l if l < h && @node[l] > @node[largest]
    r = 2 * i + 2
    largest = r if r < h && @node[r] > @node[largest]

    while largest != i
      @node[i], @node[largest] = @node[largest], @node[i]
      i = largest
      l = 2 * i + 1
      largest = l if l < h && @node[l] > @node[largest]
      r = 2 * i + 2
      largest = r if r < h && @node[r] > @node[largest]
    end
  end
  def down_heap(i)
    p = (i+1)/2-1
    while i > 0 && @node[p] < @node[i]
      @node[i], @node[p] = @node[p], @node[i]
      i = p
      p = (i+1)/2-1
    end
  end
end


INF = 1.0 / 0.0

class Node
  attr_accessor :i, :c, :prev, :d, :pot, :ans
  def initialize(i)
    @i = i
    @c = {}
    @ans = {}
    @prev = nil
    @d = INF
    @pot = 0
  end
  def <(other)
    if self.d > other.d
      return true
    else
      return false
    end
  end
  def >(other)
    if self.d < other.d
      return true
    else
      return false
    end
  end
end

nv, ne, f = gets.split.map(&:to_i)
g = Array.new(nv){|i| Node.new(i)}

ne.times{|i|
  u, v, c, d = gets.split.map(&:to_i)
  g[u].c[v] = [c, d]
  g[u].ans[v] = [0,d]
}


loop do
  nv.times{|i|
    g[i].d = INF
    g[i].prev = nil
  }
  g[0].d = 0
  q = PQueue.new

  nv.times{|i|
    q.insert(g[i])
  }

  while q.node.size > 0
    u = q.extract
    u.c.each{|v, val|
      alt = u.d + val[1]
      if g[v].d > alt
        q.delete(g[v])
        g[v].d = alt
        g[v].prev = u.i
        q.insert(g[v])
      end
    }
  end

  # p g
  max = f
  c = nv-1
  path = [c]
  while c != 0
    p = g[c].prev
    if p == nil
      puts "-1"
      exit
    end
    path.unshift(p)
    max = g[p].c[c][0] if max > g[p].c[c][0]
    c = p
  end

  # p path
  # p max

  if max < f then
    #make potential
    path.each{|i|
      g[i].pot -= g[i].d
    }
    (path.size-1).times{|i|
      u = path[i]
      v = path[i+1]
      g[u].ans[v][0] += max
    }
#    p g
    f -= max
  else
    (path.size-1).times{|i|
      u = path[i]
      v = path[i+1]
      g[u].ans[v][0] += f
    }
    break
  end
  
  #make sub-network
  (path.size-1).times{|i|
    u = path[i]
    v = path[i+1]
    g[v].c[u] ||= [0, -g[u].c[v][1]]
    g[v].c[u][0] += max
    
    g[u].c[v][0] -= max
    if g[u].c[v][0] == 0
      g[u].c.delete(v)
    end
  }

  #make modified sub-network
  g.size.times{|i|
    g[i].c.each{|j, val|
#      p "#{g[i].c[j][1]} #{g[i].pot} #{g[j].pot}"
      g[i].c[j][1] -= g[i].pot - g[j].pot
    }
  }

  # g.size.times{|i|
  #   p g[i]
  # }
end

sum = 0
nv.times{|i|
  g[i].ans.each{|k,v|
    sum += v[0]*v[1]
  }
}
puts sum