class MinCostFlow:

    def __init__(self, n):

        self.n = n

        self.G = [[] for i in range(n)]



    def addEdge(self, f, t, cap, cost):

        # [to, cap, cost, rev]

        self.G[f].append([t, cap, cost, len(self.G[t])])

        self.G[t].append([f, 0, -cost, len(self.G[f])-1])



    def minCostFlow(self, s, t, f):

        n = self.n

        G = self.G

        prevv = [0]*n; preve = [0]*n

        INF = 10**9+7



        res = 0

        while f:

            dist = [INF]*n

            dist[s] = 0

            update = 1

            while update:

                update = 0

                for v in range(n):

                    if dist[v] == INF:

                        continue

                    gv = G[v]

                    for i in range(len(gv)):

                        to, cap, cost, rev = gv[i]

                        if cap > 0 and dist[v] + cost < dist[to]:

                            dist[to] = dist[v] + cost

                            prevv[to] = v; preve[to] = i

                            update = 1

            if dist[t] == INF:

                return -1



            d = f; v = t

            while v != s:

                d = min(d, G[prevv[v]][preve[v]][1])

                v = prevv[v]

            f -= d

            res += d * dist[t]

            v = t

            while v != s:

                e = G[prevv[v]][preve[v]]

                e[1] -= d

                G[v][e[3]][1] += d

                v = prevv[v]

        return res



n, m, f = list(map(int, input().split()))

graph = MinCostFlow(n)

for i in range(m):

    u, v, c, d = list(map(int, input().split()))

    graph.addEdge(u, v, c, d)

print((graph.minCostFlow(0, n-1, f)))


from heapq import heappush, heappop

class MinCostFlow:

    INF = 10**18



    def __init__(self, N):

        self.N = N

        self.G = [[] for i in range(N)]



    def add_edge(self, fr, to, cap, cost):

        G = self.G

        G[fr].append([to, cap, cost, len(G[to])])

        G[to].append([fr, 0, -cost, len(G[fr])-1])



    def flow(self, s, t, f):

        N = self.N; G = self.G

        INF = MinCostFlow.INF



        res = 0

        H = [0]*N

        prv_v = [0]*N

        prv_e = [0]*N



        while f:

            dist = [INF]*N

            dist[s] = 0

            que = [(0, s)]



            while que:

                c, v = heappop(que)

                if dist[v] < c:

                    continue

                for i, (w, cap, cost, rev) in enumerate(G[v]):

                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:

                        dist[w] = r = dist[v] + cost + H[v] - H[w]

                        prv_v[w] = v

                        prv_e[w] = i

                        heappush(que, (r, w))

            if dist[t] == INF:

                return -1



            for i in range(N):

                H[i] += dist[i]



            d = f; v = t

            while v != s:

                d = min(d, G[prv_v[v]][prv_e[v]][1])

                v = prv_v[v]

            f -= d

            res += d * H[t]

            v = t

            while v != s:

                e = G[prv_v[v]][prv_e[v]]

                e[1] -= d

                G[v][e[3]][1] += d

                v = prv_v[v]

        return res





import sys

readline = sys.stdin.readline

write = sys.stdout.write

N, M, F = list(map(int, readline().split()))



mcf = MinCostFlow(N)

for i in range(M):

    u, v, c, d = list(map(int, readline().split()))

    mcf.add_edge(u, v, c, d)

write("%d\n" % mcf.flow(0, N-1, F))

class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.G = [[] for i in range(n)]

    def addEdge(self, f, t, cap, cost):
        # [to, cap, cost, rev]
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f]) - 1])

    def minCostFlow(self, s, t, f):
        n = self.n
        G = self.G
        prevv = [0] * n
        preve = [0] * n
        INF = 10**9 + 7
        res = 0
        while f:
            dist = [INF] * n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v
                            preve[to] = i
                            update = 1
            if dist[t] == INF:
                return -1
            d = f
            v = t
            while v != s:
                d = min(d, G[prevv[v]][preve[v]][1])
                v = prevv[v]
            f -= d
            res += d * dist[t]
            v = t
            while v != s:
                e = G[prevv[v]][preve[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prevv[v]
        return res


n, m, f = list(map(int, input().split()))
graph = MinCostFlow(n)
for i in range(m):
    u, v, c, d = list(map(int, input().split()))
    graph.addEdge(u, v, c, d)
print((graph.minCostFlow(0, n - 1, f)))

from heapq import heappush, heappop


class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

    def flow(self, s, t, f):
        N = self.N
        G = self.G
        INF = MinCostFlow.INF
        res = 0
        H = [0] * N
        prv_v = [0] * N
        prv_e = [0] * N
        while f:
            dist = [INF] * N
            dist[s] = 0
            que = [(0, s)]
            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, rev) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v
                        prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1
            for i in range(N):
                H[i] += dist[i]
            d = f
            v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res


import sys

readline = sys.stdin.readline
write = sys.stdout.write
N, M, F = list(map(int, readline().split()))
mcf = MinCostFlow(N)
for i in range(M):
    u, v, c, d = list(map(int, readline().split()))
    mcf.add_edge(u, v, c, d)
write("%d\n" % mcf.flow(0, N - 1, F))

+from heapq import heappush, heappop + + -    def __init__(self, n): -        self.n = n -        self.G = [[] for i in range(n)] +    INF = 10**18 -    def addEdge(self, f, t, cap, cost): -        # [to, cap, cost, rev] -        self.G[f].append([t, cap, cost, len(self.G[t])]) -        self.G[t].append([f, 0, -cost, len(self.G[f]) - 1]) +    def __init__(self, N): +        self.N = N +        self.G = [[] for i in range(N)] -    def minCostFlow(self, s, t, f): -        n = self.n +    def add_edge(self, fr, to, cap, cost): -        prevv = [0] * n -        preve = [0] * n -        INF = 10**9 + 7 +        G[fr].append([to, cap, cost, len(G[to])]) +        G[to].append([fr, 0, -cost, len(G[fr]) - 1]) + +    def flow(self, s, t, f): +        N = self.N +        G = self.G +        INF = MinCostFlow.INF +        H = [0] * N +        prv_v = [0] * N +        prv_e = [0] * N -            dist = [INF] * n +            dist = [INF] * N -            update = 1 -            while update: -                update = 0 -                for v in range(n): -                    if dist[v] == INF: -                        continue -                    gv = G[v] -                    for i in range(len(gv)): -                        to, cap, cost, rev = gv[i] -                        if cap > 0 and dist[v] + cost < dist[to]: -                            dist[to] = dist[v] + cost -                            prevv[to] = v -                            preve[to] = i -                            update = 1 +            que = [(0, s)] +            while que: +                c, v = heappop(que) +                if dist[v] < c: +                    continue +                for i, (w, cap, cost, rev) in enumerate(G[v]): +                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]: +                        dist[w] = r = dist[v] + cost + H[v] - H[w] +                        prv_v[w] = v +                        prv_e[w] = i +                        heappush(que, (r, w)) +            for i in range(N): +                H[i] += dist[i] -                d = min(d, G[prevv[v]][preve[v]][1]) -                v = prevv[v] +                d = min(d, G[prv_v[v]][prv_e[v]][1]) +                v = prv_v[v] -            res += d * dist[t] +            res += d * H[t] -                e = G[prevv[v]][preve[v]] +                e = G[prv_v[v]][prv_e[v]] -                v = prevv[v] +                v = prv_v[v] -n, m, f = list(map(int, input().split())) -graph = MinCostFlow(n) -for i in range(m): -    u, v, c, d = list(map(int, input().split())) -    graph.addEdge(u, v, c, d) -print((graph.minCostFlow(0, n - 1, f))) +import sys + +readline = sys.stdin.readline +write = sys.stdout.write +N, M, F = list(map(int, readline().split())) +mcf = MinCostFlow(N) +for i in range(M): +    u, v, c, d = list(map(int, readline().split())) +    mcf.add_edge(u, v, c, d) +write("%d\n" % mcf.flow(0, N - 1, F))