# scipy.sparse.csgraph.maximum_flow は現在32bit整数型しか扱えない 想定WA
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow

N, M, K = map(int, input().split())

A = [-1] * M
B = [-1] * M
C = [-1] * M
D = [-1] * M

c2i = []
for i in range(M):
    A[i], B[i], C[i], D[i] = map(int, input().split())
    c2i.append((C[i], i))
c2i.sort()

X = [0] * M

for ci, i in c2i:
    mf = [[0] * (N + 2) for _ in range(N + 2)]
    mf[0][A[i]] += K * N
    mf[0][B[i]] += K * N
    for a, b, x in zip(A, B, X):
        mf[0][a] += x
        mf[a][b] += x
    for j in range(N):
        mf[j + 1][N + 1] += K
    X[i] = min(D[i], round(maximum_flow(csr_matrix(mf), 0, N + 1).flow_value) - K - sum(X))

if sum(X) < K * (N - 1):
    print(-1)
else:
    print(sum([c * x for c, x in zip(C, X)]))