#include <bits/stdc++.h>


using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 10;
const int MA = 250'000;
struct Point
{
	int x;
	int y;
	int color;
	Point() {}
	Point(int x, int y, int color) : x(x), y(y), color(color){}
	bool operator < (const Point &o) const {
		if (y != o.y) return y < o.y;
		return x < o.x;
	}
}p[N];


struct SegmentTree{
	struct Node {
		int l;
		int r;
		int val;
		int lazy;
	} node[4 * MA];
	tuple<int, int> lrnode(int id) {
		return make_tuple(2*id, 2*id + 1);
	}
	void build(int id, int l, int r) {
		node[id].l = l;
		node[id].r = r;
		node[id].val = node[id].lazy = 0;	
		if (l == r) return;
		int mid = l + r >> 1;
		auto [lnode, rnode] = lrnode(id);
		build(lnode, l, mid);
		build(rnode, mid + 1, r);
		return;
	}
	void push(int id) {
		if (node[id].l == node[id].r || node[id].lazy == 0) return;
		auto [lnode, rnode] = lrnode(id);
		int lazy = node[id].lazy;
		
		node[lnode].val += lazy;
		node[lnode].lazy += lazy;
		
		node[rnode].val += lazy;
		node[rnode].lazy += lazy;
		
		node[id].lazy = 0;
	}
	void update(int id, int l, int r, int val) {
		
		if (node[id].l >= l && node[id].r <= r) {
			node[id].val += val;
			node[id].lazy += val;
			
		} else {
			if (node[id].l > r || node[id].r < l) return;
			push(id);
			auto [lnode, rnode] = lrnode(id);
			update(lnode, l, r, val);
			update(rnode, l, r, val);
			node[id].val = max(node[lnode].val, node[rnode].val);
		}
		// cout << "update " << id << " " << l << " "<< r << " " << val << ":" <<  node[id].val << endl;
	}
}seg;

int n, k;

bool can_do(int len) {
	vector<Point> events;
	for (int i = 1; i <= n; i++) {
		auto [x, y, color] = p[i];
		events.emplace_back(x, y, color);
		if (y + len + 1 <= MA)
			events.emplace_back(x, y + len + 1, -color);
	}
	seg.build(1, 1, MA);
	sort(events.begin(), events.end());
	multiset<int> color_pos[N];
	for (int i = 0; i < events.size(); ) {
		int cur_y = events[i].y, pt = i;
		// cout << "at y = " << cur_y << endl;
		for (; pt < events.size() && events[pt].y == cur_y; ++pt) {
			auto [x, y, color] = events[pt];
			// cout << x << " " << color << "--" << endl;
			int acolor = abs(color);
			int l = x, r = min(x + len, MA);
			auto &cur_mset = color_pos[acolor];
			if (cur_mset.empty()) {
				assert(color > 0);
				seg.update(1, l, r, 1);
				cur_mset.insert(x);
				continue;
			}
			auto lb = cur_mset.lower_bound(x);
			if (lb != cur_mset.begin()) {
				int lf = *prev(lb);
				l = max(l, lf + len + 1);
			}
			if (lb != cur_mset.end()) {
				int rg = color > 0 ? *lb : (next(lb) == cur_mset.end() ? MA + 1 : *next(lb));
				r = min(r, rg - 1);
			}
			// cout << "l = " << l << " r = " << r << endl;
			if (l <= r) {
				seg.update(1, l, r, color < 0 ? -1 : 1);
			}
			if (color < 0) 
				cur_mset.erase(lb);
			else
				cur_mset.insert(x);

		}
		if (seg.node[1].val >= k) return true;
		i = pt;
	}
	return false;
}


int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y >> p[i].color;
	}
	int ma = 250'000, mi = 0;
	while (mi < ma) {
		int mid = ma + mi >> 1;
		// cout << "at mid = " << mid;
		if (can_do(mid)) {
			ma = mid;
		} else {
			mi = mid + 1;
		}
	}
	cout << mi;
}