#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using i64=int_least64_t;

namespace std
{
    // hash
    template <class T> size_t hash_combine(size_t seed, T const &key) { return seed ^ (hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); }
    template <class T, class U> struct hash<pair<T, U>> { size_t operator()(pair<T, U> const &pr) const { return hash_combine(hash_combine(0, pr.first), pr.second); } };
    template <class tuple_t, size_t index = tuple_size<tuple_t>::value - 1> struct tuple_hash_calc { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(tuple_hash_calc<tuple_t, index - 1>::apply(seed, t), get<index>(t)); } };
    template <class tuple_t> struct tuple_hash_calc<tuple_t, 0> { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(seed, get<0>(t)); } };
    template <class... T> struct hash<tuple<T...>> { size_t operator()(tuple<T...> const &t) const { return tuple_hash_calc<tuple<T...>>::apply(0, t); } };
    // iostream
    template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { return is >> p.first >> p.second; }
    template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << p.first << ' ' << p.second; }
    template <class tuple_t, size_t index> struct tupleis { static istream &apply(istream &is, tuple_t &t) { tupleis<tuple_t, index - 1>::apply(is, t); return is >> get<index>(t); } };
    template <class tuple_t> struct tupleis<tuple_t, SIZE_MAX> { static istream &apply(istream &is, tuple_t &t) { return is; } };
    template <class... T> istream &operator>>(istream &is, tuple<T...> &t) { return tupleis<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(is, t); }
    template <> istream &operator>>(istream &is, tuple<> &t) { return is; }
    template <class tuple_t, size_t index> struct tupleos { static ostream &apply(ostream &os, const tuple_t &t) { tupleos<tuple_t, index - 1>::apply(os, t); return os << ' ' << get<index>(t); } };
    template <class tuple_t> struct tupleos<tuple_t, 0> { static ostream &apply(ostream &os, const tuple_t &t) { return os << get<0>(t); } };
    template <class... T> ostream &operator<<(ostream &os, const tuple<T...> &t) { return tupleos<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(os, t); }
    template <> ostream &operator<<(ostream &os, const tuple<> &t) { return os; }
    template <class Container, typename Value = typename Container::value_type, enable_if_t<!is_same<decay_t<Container>, string>::value, nullptr_t> = nullptr>
    istream& operator>>(istream& is, Container &cont) { for(auto&& e : cont) is >> e; return is; }
    template <class Container, typename Value = typename Container::value_type, enable_if_t<!is_same<decay_t<Container>, string>::value, nullptr_t> = nullptr>
    ostream& operator<<(ostream& os, const Container &cont) { bool flag = 1; for(auto&& e : cont) flag ? flag = 0 : (os << ' ', 0), os << e; return os; }
} // namespace std

#include <cassert>
#include <list>
#include <vector>

// Base class of flow algorithms
template <class cap_t, class cost_t>
struct flow_base
{
    struct edge_t
    {
        size_t src, dst;
        cap_t cap; cost_t cost;
        edge_t *rev;
        edge_t(size_t _src, size_t _dst, cap_t _cap, cost_t _cost, edge_t *_rev)
            : src(_src), dst(_dst), cap(_cap), cost(_cost), rev(_rev) {}
    }; // struct edge_t

protected:
    using adj_type = std::vector<std::list<edge_t>>;
    adj_type adj;

public:
    flow_base(size_t _n = 0) : adj(_n) {}

    flow_base(const flow_base& other) : adj(other.size())
    {
        for(size_t node{0}; node != other.size(); ++node)
        {
            for(const auto &e : other[node])
            {
                if(e.src == node)
                {
                    adj[e.src].emplace_back(e);
                    adj[e.dst].emplace_back(*e.rev);
                    adj[e.src].back().rev = &adj[e.dst].back();
                    adj[e.dst].back().rev = &adj[e.src].back();
                    e.rev->src = -1;
                }
                else
                {
                    e.rev->rev->src = node;
                }
            }
        }
    }

    flow_base &operator=(const flow_base &other)
    {
        if(this != &other)
        {
            flow_base cop(other);
            std::swap(adj, cop.adj);
        }
        return *this;
    }

    size_t size() const { return adj.size(); }

    typename decltype(adj)::reference operator[](size_t node) { assert(node < size()); return adj[node]; }
    typename decltype(adj)::const_reference operator[](size_t node) const { assert(node < size()); return adj[node]; }

    void add_edge(size_t src, size_t dst, cap_t cap, cost_t cost)
    {
        assert(src < size()); assert(dst < size());
        if(cap <= 0) return;
        adj[src].emplace_back(src, dst, cap, cost, nullptr);
        adj[dst].emplace_back(dst, src, 0, -cost, nullptr);
        adj[src].back().rev = &adj[dst].back();
        adj[dst].back().rev = &adj[src].back();
    }
}; // struct flow_base


template <class cap_t, class cost_t>
class min_cost_flow : public flow_base<cap_t, cost_t>
{
    using base = flow_base<cap_t, cost_t>;
    using edge_t = typename base::edge_t;

    template <class type>
    constexpr bool valid(const type &val) const { return val != static_cast<type>(-1); }

    template <class type>
    constexpr void make_invalid(type &val) const { val = -1; }

    cost_t min_cost, total_cost;
    std::vector<cap_t> supp;
    std::vector<cost_t> ptnl;

    void copy_member(const min_cost_flow &other)
    {
        min_cost = other.min_cost;
        total_cost = other.total_cost;
        supp = other.supp;
        ptnl = other.ptnl;
    }

    void Dijkstra(std::vector<edge_t*> &last)
    {
        const cost_t infty(total_cost + 1);
        std::vector<cost_t> dist(base::size(), infty);
        //*/ // O((V + E)logV)
        std::priority_queue<std::pair<cost_t, size_t>> que;
        for(size_t node{}; node != base::size(); ++node)
        {
            if(supp[node] > static_cast<cap_t>(0))
            {
                dist[node] = 0;
                que.emplace(0, node);
            }
        }
        while(!que.empty())
        {
            // auto [nsp, node] = que.top();
            cost_t nsp; size_t node;
            std::tie(nsp, node) = que.top();
            que.pop();
            if(-nsp != dist[node]) continue;
            ptnl[node] -= nsp;
            if(ptnl[node] > infty) ptnl[node] = infty;
            make_invalid(dist[node]);
            for(edge_t &e : base::adj[node])
            {
                if(!valid(dist[e.dst]) || e.cap == static_cast<cap_t>(0)) continue;
                if(dist[e.dst] + ptnl[e.dst] > ptnl[node] + e.cost)
                {
                    dist[e.dst] = ptnl[node] + e.cost - ptnl[e.dst];
                    last[e.dst] = &e;
                    que.emplace(-dist[e.dst], e.dst);
                }
            }
        }
        /*/ // O(V^2)
        //*/
    }

public:
    min_cost_flow(size_t _n = 0) : base::flow_base(_n), min_cost(0), total_cost(0), supp(_n), ptnl(_n)  {}

    min_cost_flow(const min_cost_flow &other) : base::flow_base(other)
    {
        copy_member(other);
    }

    min_cost_flow &operator=(const min_cost_flow &other)
    {
        base::operator=(other);
        copy_member(other);
        return *this;
    }

    void add_edge(size_t src, size_t dst, cap_t cap, cost_t cost)
    {
        assert(src != dst);
        if(cap <= static_cast<cap_t>(0)) return;
        if(cost < static_cast<cost_t>(0))
        {
            supp[src] -= cap;
            supp[dst] += cap;
            min_cost += cap * cost;
            total_cost -= cap * cost;
            base::add_edge(dst, src, cap, -cost);
        }
        else
        {
            total_cost += cap * cost;
            base::add_edge(src, dst, cap, cost);
        }
    }

    void supply(size_t node, cap_t vol) { supp[node] += vol; }

    bool solve()
    {
        for(bool aug = true; aug; )
        {
            aug = false;
            std::vector<edge_t*> last(base::size());
            Dijkstra(last);
            std::vector<bool> shut(base::size());
            for(size_t dst{}; dst != base::size(); ++dst)
            {
                if(supp[dst] < static_cast<cap_t>(0) and last[dst])
                {
                    cap_t resid{-supp[dst]};
                    size_t src{dst}, block;
                    make_invalid(block);
                    while(last[src] && !shut[src])
                    {
                        if(resid >= last[src]->cap) resid = last[block = src]->cap;
                        src = last[src]->src;
                    }
                    if(shut[src]) block = src;
                    else
                    {
                        if(resid >= supp[src])
                        {
                            resid = supp[src];
                            block = src;
                        }
                        for(size_t node{dst}; node != src; node = last[node]->src)
                        {
                            last[node]->cap -= resid;
                            last[node]->rev->cap += resid;
                        }
                        supp[src] -= resid;
                        supp[dst] += resid;
                        min_cost += ptnl[dst] * resid;
                        aug = true;
                    }
                    if(valid(block))
                    {
                        for(size_t node{dst}; node != block; node = last[node]->src) shut[node] = true;
                        shut[block]=true;
                    }
                }
            }
        }
        for(cap_t s : supp) if(s > static_cast<cap_t>(0)) return false;
        return true;
    }

    cost_t optimal() { assert(solve()); return min_cost; }
};

main()
{
    int n,m,f; cin>>n>>m>>f;
    min_cost_flow<int,int> mcf(n);
    while(m--)
    {
        int a,b; cin>>a>>b;
        int c,d; cin>>c>>d;
        mcf.add_edge(a,b,c,d);
    }
    mcf.supply(0,f);
    mcf.supply(n-1,-f);
    if(mcf.solve()) cout << mcf.optimal() << "\n";
    else cout << -1 << "\n";
}



Measured memory_bytes: 3276