#include <cstdio>
#include <vector>

using namespace std;

const int maxn = 404;
const int inf = 3000000;

FILE *in = fopen("renovare.in","r"), *out = fopen("renovare.out","w");

vector<int> a[maxn];
int costuri[maxn][maxn];
int fluxuri[maxn][maxn];
int f[maxn][maxn];
int n, m, x;
int g;

char added[maxn][maxn];
void read()
{
    fscanf(in, "%d %d %d", &n, &m, &x);

    int p, q, c, cst;
    int tmp = 0;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d %d %d", &p, &q, &c, &cst);
        tmp = q + 1;
        //if ( !added[p+1][tmp] )
        //{
            a[p+1].push_back(tmp), added[p+1][tmp] = 1;
            fluxuri[p+1][tmp] = c;
            costuri[p+1][tmp] = 0;
        //}

        tmp = q + n + 1;
        //if ( !added[p+1][tmp] )
        //{
            costuri[p+1][tmp] = cst;
            a[p+1].push_back(tmp), added[p+1][tmp] = 1;
            fluxuri[p+1][tmp] = inf;
        //}

        tmp = q + 1;
        //if ( !added[q+n+1][tmp] )
        //{
            a[q+n+1].push_back(tmp), added[q+n+1][tmp] = 1;
            fluxuri[q+n+1][tmp] = inf;
            costuri[q+n+1][tmp] = 0;
        //}
    }
    a[1].push_back(2);
    fluxuri[1][2] = x;
    costuri[1][2] = 0;

    g = n + n + 2;
}

int C[maxn*maxn];
int viz[maxn];
int cst[maxn];

int BF()
{
    for ( int i = 1; i < g; ++i )
        viz[i] = 0, cst[i] = inf;
    cst[1] = 0;
    int p = 0, u = 0;
    C[p] = 1;
    viz[1] = 1;

    while ( p <= u )
    {
        int X = C[p++];
        int k = (int)a[X].size();

        for ( int i = 0; i < k; ++i )
            if ( f[X][ a[X][i] ] < fluxuri[X][ a[X][i] ] )
                if ( cst[X] + costuri[X][ a[X][i] ] < cst[ a[X][i] ] )
                {
                    cst[ a[X][i] ] = cst[X] + costuri[X][ a[X][i] ];
                    viz[ a[X][i] ] = X;

                    C[++u] = a[X][i];
                }
    }

    return viz[n+1];
}

inline int min(int x, int y)
{
    return x < y ? x : y;
}

int L[maxn];
int answ = 0;
void flow()
{
    int lg;
    while ( BF() )
    {
        lg = 0;
        L[lg] = n + 1;
        int v = inf;

        while ( L[lg] != 1 )
        {
            ++lg;
            int k2 = L[lg-1];

            L[lg] = viz[ k2 ];
            int k1 = L[lg];

            v = min(v, fluxuri[ k1 ][ k2 ] - f[ k1 ][ k2 ]);
        }

        for ( int i = lg; i; --i )
        {
            int k1 = L[i], k2 = L[i-1];
            f[ k1 ][ k2 ] += v;
            f[ k2 ][ k1 ] -= v;

            int t = costuri[k1][k2];
            if ( t > 0  )
                answ += v * t;
        }
    }
}


int main()
{
    read();
    flow();

    for ( int i = 1; i <= n+n+1; ++i )
    {
        printf("%d: ", i);
        for ( int j = 0; j < a[i].size(); ++j )
            printf("%d ", a[i][j]);
        printf("\n");
    }

//    for ( int i = 1; i <= n+n; ++i )
//    {
//        for ( int j = 1; j <= n+n; ++j )
//            printf("%d ", a[i][j].flux);
//        printf("\n");
//    }
//    printf("\n\n");
//    for ( int i = 1; i <= n+n+1; ++i )
//    {
//        for ( int j = 1; j <= n+n+1; ++j )
//            printf("%d ", f[i][j]);
//        printf("\n");
//    }
    fprintf(out, "%d\n", answ);



    return 0;
}