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

#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define mset(s,t) memset(s,t,sizeof(s))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define SZ(x) ((int)x.size())
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second

template<class T1,class T2>bool ckmax(T1 &a,T2 b){if(a<b)return a=b,1;else return 0;}
template<class T1,class T2>bool ckmin(T1 &a,T2 b){if(a>b)return a=b,1;else return 0;}

inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
    return f?-x:x;
}
template<typename T>void print(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
template<typename T>void print(T x,char ch){
    print(x),putchar(ch);
}

const int N=400005;

struct node{
    int x,y,c;
}a[N];

int n,K;

struct Line{
    int x,l,r,c,opt;
    friend bool operator < (const Line&a,const Line&b){
        return a.x!=b.x?a.x<b.x:a.opt<b.opt;
    }
}b[N];
int tmp[N],len,m;

struct SMT{
    #define ls (u<<1)
    #define rs (u<<1|1)

    int maxx[N<<2],lazy[N<<2];
    void pushup(int u){
        maxx[u]=max(maxx[ls],maxx[rs]);
    }
    void pushadd(int u,int dlt){
        maxx[u]+=dlt,lazy[u]+=dlt;
    }
    void pushdown(int u){
        pushadd(ls,lazy[u]),pushadd(rs,lazy[u]),lazy[u]=0;
    }
    void build(int u,int l,int r){
        maxx[u]=lazy[u]=0;
        if(l==r)return;
        int mid=l+r>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void update(int u,int l,int r,int ql,int qr,int dlt){
        if(ql<=l&&r<=qr){
            pushadd(u,dlt);
            return;
        }
        pushdown(u);
        int mid=l+r>>1;
        if(ql<=mid)update(ls,l,mid,ql,qr,dlt);
        if(qr>mid)update(rs,mid+1,r,ql,qr,dlt);
        pushup(u);
    }
}smt;

multiset<pii>s[100005];

bool check(int R){
    m=len=0;
    rep(i,1,K)s[i].clear();
    rep(i,1,n){
        b[++m]={a[i].x,a[i].y,a[i].y+R,a[i].c,1};
        b[++m]={a[i].x+R+1,a[i].y,a[i].y+R,a[i].c,-1};
        tmp[++len]=a[i].y,tmp[++len]=a[i].y+R;
        // tmp[++len]=a[i].y-1,tmp[++len]=a[i].y+R+1;
    }
    sort(tmp+1,tmp+len+1),len=unique(tmp+1,tmp+len+1)-tmp-1;
    sort(b+1,b+m+1);
    smt.build(1,1,len);
    rep(i,1,m){
        b[i].l=lower_bound(tmp+1,tmp+len+1,b[i].l)-tmp;
        b[i].r=lower_bound(tmp+1,tmp+len+1,b[i].r)-tmp;
        int _l=b[i].l,_r=b[i].r;
        // printf("b[%d]=(l=%d,r=%d,c=%d,opt=%d)\n",i,b[i].l,b[i].r,b[i].c,b[i].opt);
        if(b[i].opt==1){
            multiset<pii>&ss=s[b[i].c];
            auto it=ss.lower_bound({b[i].l,-1});
            if(it!=ss.end())ckmin(b[i].r,it->fir-1);
            if(it!=ss.begin())it--,ckmax(b[i].l,it->sec+1);
            if(b[i].l<=b[i].r)smt.update(1,1,len,b[i].l,b[i].r,1);
            ss.insert({_l,_r});
        }else{
            multiset<pii>&ss=s[b[i].c];
            ss.erase(ss.lower_bound({_l,_r}));
            auto it=ss.lower_bound({b[i].l,-1});
            if(it!=ss.end())ckmin(b[i].r,it->fir-1);
            if(it!=ss.begin())it--,ckmax(b[i].l,it->sec+1);
            if(b[i].l<=b[i].r)smt.update(1,1,len,b[i].l,b[i].r,-1);
        }
        if(smt.maxx[1]==K)return 1;
    }
    return 0;
}

int main(){
    n=read(),K=read();
    rep(i,1,n)a[i].x=read(),a[i].y=read(),a[i].c=read();

    // check(5);
    // return 0;
    // printf("check(5)=%d\n",check(5));
    // return 0;

    int l=0,r=250000;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    print(l,'\n');
    return 0;
}