#include <bits/stdc++.h>
using namespace std;

const int TAP = 0;
const int SINK = 201;
const int MAXNODE = 202;
const int PREF = 101;

int G[MAXNODE][MAXNODE];
int c[MAXNODE][MAXNODE];
int d[MAXNODE];
int p[MAXNODE];
int K, A, V, M;

void read_input(void) {
    for (int i(0); i < MAXNODE; ++i)
        fill(c[i], c[i] + MAXNODE, 1e9);
    for (int i(1); i <= 100; ++i)
    {
        c[TAP][i] = 0;
        c[i][TAP] = 0;
        c[i+PREF][SINK] = 0;
        c[SINK][i+PREF] = 0;
        G[TAP][i] = 1;
        G[i+PREF][SINK] = 1;
    }
    cin >> A >> V >> M >> K;

    for (int i(0); i < M; ++i)
    {
        int u, v, cost;
        cin >> u >> v >> cost;
        ++u;
        v = v + 1 + PREF;
        G[u][v]++;
        c[u][v] = -cost;
        c[v][u] = cost;
    }
}

int bellman_ford(int t, int s)
{
    fill(d, d + MAXNODE, 1e9);
    fill(p, p + MAXNODE, -1);

    d[t] = 0;
    for (int i(0); i < MAXNODE; ++i)
        for (int j(0); j < MAXNODE; ++j)
            if (d[j] != 1e9)
                for (int k(0); k < MAXNODE; ++k)
                    if (G[j][k] > 0 and d[k] > d[j] + c[j][k])
                    {
                        d[k] = d[j] + c[j][k];
                        p[k] = j;
                    }
    return -d[s];
}

int solve(int t, int s)
{
    int ans(0);
    for (int i(0); i < K; ++i) {
        ans += bellman_ford(t, s);
        int cur = s;
        while (cur != t) {
            G[p[cur]][cur]--;
            G[cur][p[cur]]++;
            cur = p[cur];
        }
    }
    return ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    read_input();
    cout << solve(TAP, SINK) << endl;
}