#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using ll = long long;
#define int ll
vector<pair<int, int>> vp[N];
int n, m, k;
int answer(int lambda) {
ll rasp = 0;
int last = 0, cst = 0, ans = 0;
for (int i = 1; i <= n; i ++) {
for (auto j : vp[i]) {
if (j.first > last) {
cst += j.second;
if (j.second < 0) {
rasp += -j.second;
}
}
}
//~ cout << i << " " << cst << " " << last << '\n';
if (cst >= lambda && ans < k) {
last = i;
cst = 0;
ans ++;
}
}
return rasp;
}
int greedy(int lambda) {
int last = 0, cst = 0, ans = 0;
for (int i = 1; i <= n; i ++) {
for (auto j : vp[i]) {
if (j.first > last) {
cst += j.second;
}
}
if (cst >= lambda) {
last = i;
cst = 0;
ans ++;
}
}
return ans;
}
signed main() {
cin >> n >> m >> k;
for (int i = 0; i < m; i ++) {
int s, t, c;
cin >> s >> t >> c;
vp[s].push_back({t, c});
vp[t].push_back({s, -c});
}
int lambda = 0;
for (int pas = 1ll << 50; pas; pas >>= 1) {
if (greedy(lambda + pas) >= k) {
lambda += pas;
}
}
//~ cout << lambda << '\n';
cout << answer(lambda) << '\n';
}
