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

using ll = int64_t;

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

	int N, K;
	cin >> N >> K;
	vector<tuple<int, int, ll>> stuff(N);
	ll total = 0;
	for (auto& [r, l, w] : stuff) {
		cin >> l >> r >> w;
		total += w;
	}
	sort(stuff.begin(), stuff.end());

	const int S = 1 << (N <= 1 ? 0 : 32 - __builtin_clz(N-1));
	vector<vector<ll>> seg(K+1, vector<ll>(2*S));
	auto query = [&](int k, int l, int r) -> ll {
		ll res = 0;
		for (int a = S+l, b = S+r; a < b; a /= 2, b /= 2) {
			if (a & 1) {
				res = max(res, seg[k][a++]);
			}
			if (b & 1) {
				res = max(res, seg[k][--b]);
			}
		}
		return res;
	};
	auto upd = [&](int k, int i, ll val) -> void {
		seg[k][S+i] = max(seg[k][S+i], val);
		for (int a = (S+i)/2; a >= 1; a /= 2) {
			seg[k][a] = max(seg[k][2*a], seg[k][2*a+1]);
		}
	};
	for (int i = 0; i < N; i++) {
		auto [r, l, w] = stuff[i];
		int j = 0;
		ll best_1 = 0;
		while (j < i) {
			int r2, l2, w2;
			tie(r2, l2, w2) = stuff[j];
			if (r2 < l) {
				ll val = query(K, j, j+1) + w;
				best_1 = max(best_1, val);
			} else {
				break;
			}
			j++;
		}
		ll pbest = best_1;
		for (int k = 1; k <= K; k++) {
			ll val = query(k-1, j, i) + w;
			pbest = max(pbest, val);
			upd(k, i, pbest);
		}
	}
	ll max_left = query(K, 0, N);
	ll ans = total - max_left;
	cout << ans << '\n';

	return 0;
}