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;
  mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
  long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
  long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
  struct node {
    long long lb, rb, ans = 0, lazy = 0;
    node *l, *r;
    node(long long lq, long long rq) {
      lb = lq;
      rb = rq;
      if (lb + 1 < rb) {
        long long mid = (lb + rb) / 2;
        l = new node(lb, mid);
        r = new node(mid, rb);
      }
    }
    void update() {
      if (lb + 1 < rb) ans = min(l->ans, r->ans);
    }
    void push() {
      ans += lazy;
      if (lb + 1 < rb) {
        l->lazy += lazy;
        r->lazy += lazy;
      }
      lazy = 0;
    }
    void add(long long lq, long long rq, long long x) {
      push();
      if (rb <= lq || rq < lb) return;
      if (lq <= lb && rb - 1 <= rq) {
        lazy += x;
        push();
        return;
      } else {
        l->add(lq, rq, x);
        r->add(lq, rq, x);
        update();
      }
    }
    long long minim(long long lq, long long rq) {
      push();
      if (rb <= lq || rq < lb) return LLONG_MAX;
      if (lq <= lb && rb - 1 <= rq)
        return ans;
      else
        return min(l->minim(lq, rq), r->minim(lq, rq));
    }
  };
  struct interval {
    long long l, r, w;
  };
  signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n, m;
    cin >> n >> m;
    vector<interval> order(n);
    for (auto &i : order) cin >> i.l >> i.r >> i.w;
    for (auto &i : order) {
      i.r--;
    }
    sort((order).begin(), (order).end(),
         [](interval a, interval b) { return a.w < b.w; });
    node d(0, m);
    long long ans = LLONG_MAX, j = 0;
    for (long long i = 0; i < n; i++) {
      while (j < n && d.minim(1, m - 1) == 0) {
        d.add(order[j].l, order[j].r, 1);
        j++;
      }
      if (d.minim(1, m - 1) > 0) ans = min(ans, order[j - 1].w - order[i].w);
      d.add(order[i].l, order[i].r, -1);
    }
    cout << ans;
    return 0;
  }
  