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 i64 = long long;
  using u64 = unsigned long long;
  struct debug {
    ~debug() { cerr << endl; }
    template <class c>
    debug& operator<<(c x) {
      cerr << x;
      return *this;
    }
    template <class c, class d>
    debug& operator<<(pair<c, d> x) {
      *this << "(" << x.first << ", " << x.second << ")";
      return *this;
    }
    template <class c>
    debug& operator<<(vector<c> x) {
      *this << "[";
      int f = 0;
      for (auto it : x) {
        *this << (f ? ", " : "");
        *this << it;
        f = 1;
      }
      *this << "]";
      return *this;
    }
  };
  struct segment {
    int l, r, w;
    segment(int _l, int _r, int _w) : l(_l), r(_r), w(_w) {}
    bool operator<(const segment& other) const { return w < other.w; }
  };
  int M = 2e6;
  vector<int> segTree(4 * M);
  vector<int> lazy(4 * M);
  void push(int idx) {
    segTree[2 * idx] += lazy[idx];
    segTree[2 * idx + 1] += lazy[idx];
    segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
    lazy[2 * idx] += lazy[idx];
    lazy[2 * idx + 1] += lazy[idx];
    lazy[idx] = 0;
  }
  void update(int ul, int ur, int val, int idx = 1, int l = 1, int r = M) {
    if (ul > ur) return;
    if (ul == l && ur == r) {
      if (l != r) {
        lazy[idx] += val;
        push(idx);
      } else {
        segTree[idx] += val;
      }
      return;
    }
    push(idx);
    int mid = (l + r) / 2;
    update(ul, min(ur, mid), val, 2 * idx, l, mid);
    update(max(ul, mid + 1), ur, val, 2 * idx + 1, mid + 1, r);
    segTree[idx] = min(segTree[2 * idx], segTree[2 * idx + 1]);
  }
  int getMin(int ql, int qr, int idx = 1, int l = 1, int r = M) {
    if (ql > qr) return 1e9;
    if (ql == l && qr == r) {
      if (l != r) {
        push(idx);
      }
      return segTree[idx];
    }
    push(idx);
    int mid = (l + r) / 2;
    return min(getMin(ql, min(mid, qr), 2 * idx, l, mid),
               getMin(max(ql, mid + 1), qr, 2 * idx + 1, mid + 1, r));
  }
  int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    M = 2 * m;
    vector<segment> v;
    for (int i = 0; i < n; i++) {
      int l, r, w;
      scanf("%d%d%d", &l, &r, &w);
      v.push_back(segment(2 * l, 2 * r, w));
    }
    sort(v.begin(), v.end());
    int ans = 1e9;
    int lP = 0;
    update(v[0].l, v[0].r, 1);
    if (getMin(2, 2 * m) == 1) ans = 0;
    for (int i = 1; i < n; i++) {
      update(v[i].l, v[i].r, 1);
      while (lP <= i) {
        update(v[lP].l, v[lP].r, -1);
        if (getMin(2, 2 * m) == 0) {
          update(v[lP].l, v[lP].r, 1);
          break;
        }
        lP++;
      }
      if (getMin(2, 2 * m) >= 1) {
        ans = min(ans, v[i].w - v[lP].w);
      }
    }
    printf("%d\n", ans);
  }
  