description: You are given n segments on a number line, numbered from 1 to n. The i-th segments covers all integer points from l_i to r_i and has a value w_i.
  
  You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point m starting from point 1 in arbitrary number of moves.
  
  The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.
  
  In every test there exists at least one good subset.
  
  Input
  
  The first line contains two integers n and m (1 ≤ n ≤ 3 ⋅ 10^5; 2 ≤ m ≤ 10^6) — the number of segments and the number of integer points.
  
  Each of the next n lines contains three integers l_i, r_i and w_i (1 ≤ l_i < r_i ≤ m; 1 ≤ w_i ≤ 10^6) — the description of the i-th segment.
  
  In every test there exists at least one good subset.
  
  Output
  
  Print a single integer — the minimum cost of a good subset.
  
  Examples
  
  Input
  
  
  5 12
  1 5 5
  3 4 10
  4 10 6
  11 12 5
  10 12 3
  
  
  Output
  
  
  3
  
  
  Input
  
  
  1 10
  1 10 23
  
  
  Output
  
  
  0
solution: #include <bits/stdc++.h>
  using namespace std;
  using lli = long long int;
  using vb = vector<bool>;
  using vc = vector<char>;
  using vd = vector<double>;
  using vi = vector<int>;
  using vvi = vector<vi>;
  using vlli = vector<lli>;
  using vvlli = vector<vlli>;
  using pi = pair<int, int>;
  using plli = pair<lli, lli>;
  int readint() {
    int q;
    scanf("%d", &q);
    return q;
  }
  lli readlong() {
    lli q;
    scanf("%lld", &q);
    return q;
  }
  double readdbl() {
    double q;
    scanf("%lf", &q);
    return q;
  }
  char readc() {
    char q;
    scanf("%c", &q);
    return q;
  }
  void printint(int q) { printf("%d", q); }
  void printlong(lli q) { printf("%lld", q); }
  void printdbl(double q, int p = 6) { printf("%.*lf", p, q); }
  void readln() { scanf("\n"); }
  void println() { printf("\n"); }
  void space() { printf(" "); }
  void print(int q) { printint(q); }
  void print(lli q) { printlong(q); }
  void print(double q) { printdbl(q); }
  void print(char c) { printf("%c", c); }
  template <typename T>
  void println(T q) {
    print(q);
    println();
  }
  template <typename T>
  void printsp(T q) {
    print(q);
    space();
  }
  template <typename T>
  T maxim(T f, T s) {
    return (f > s) ? f : s;
  }
  template <typename T>
  T minim(T f, T s) {
    return (f < s) ? f : s;
  }
  template <typename T>
  T abs(T arg) {
    return arg < 0 ? -arg : arg;
  }
  const lli mod = 998244353;
  map<int, vector<pi>> segm;
  const int N = 1e6 + 1;
  int n, m;
  int t[2 * N];
  int h;
  int d[N];
  void apply(int p, int value) {
    t[p] += value;
    if (p < m) d[p] += value;
  }
  void build(int p) {
    while (p > 1) p >>= 1, t[p] = minim(t[p << 1], t[p << 1 | 1]) + d[p];
  }
  void push(int p) {
    for (int s = h; s > 0; --s) {
      int i = p >> s;
      if (d[i] != 0) {
        apply(i << 1, d[i]);
        apply(i << 1 | 1, d[i]);
        d[i] = 0;
      }
    }
  }
  void inc(int l, int r, int value) {
    l += m, r += m;
    int l0 = l, r0 = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) apply(l++, value);
      if (r & 1) apply(--r, value);
    }
    build(l0);
    build(r0 - 1);
  }
  int query(int l, int r) {
    l += m, r += m;
    push(l);
    push(r - 1);
    int res = t[l];
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = minim(res, t[l++]);
      if (r & 1) res = minim(t[--r], res);
    }
    return res;
  }
  int main() {
    n = readint();
    m = readint();
    h = sizeof(int) * 8 - __builtin_clz(m);
    for (int i = 0; i < n; ++i) {
      int l = readint() - 1;
      int r = readint() - 1;
      int w = readint();
      segm[w].push_back(make_pair(l, r));
    }
    vi w;
    for (auto x : segm) w.push_back(x.first);
    int res = *w.rbegin() - *w.begin();
    auto top = -1;
    auto bottom = 0;
    while (top < int(w.size()) - 1) {
      {
        do {
          top++;
          for (auto s : segm[w[top]]) {
            inc(s.first, s.second, 1);
          }
        } while (query(0, m - 1) == 0 && top < int(w.size()) - 1);
        if (query(0, m - 1) > 0) {
          res = minim(res, w[top] - w[bottom]);
          do {
            for (auto s : segm[w[bottom]]) {
              inc(s.first, s.second, -1);
            }
            bottom++;
            if (query(0, m - 1) > 0) res = minim(res, w[top] - w[bottom]);
          } while (query(0, m - 1) > 0 && top - bottom + 1 > 0);
        } else
          break;
      }
    }
    println(res);
    return 0;
  }
  