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;
  int n, m;
  struct seg {
    int t[3000300 << 2], ad[3000300 << 2];
    inline void up(int k) { t[k] = min(t[k << 1], t[k << 1 | 1]); }
    void build(int k, int l, int r) {
      ad[k] = 0;
      if (l == r) return t[k] = 0, void();
      int m = l + r >> 1;
      build(k << 1, l, m), build(k << 1 | 1, m + 1, r);
      up(k);
    }
    inline void down(int k) {
      t[k << 1] += ad[k], t[k << 1 | 1] += ad[k];
      ad[k << 1] += ad[k], ad[k << 1 | 1] += ad[k];
      ad[k] = 0;
    }
    void cover(int k, int l, int r, int L, int R, int v) {
      if (l >= L && r <= R) {
        t[k] += v, ad[k] += v;
        return;
      }
      if (ad[k] != 0) down(k);
      int m = l + r >> 1;
      if (L <= m) cover(k << 1, l, m, L, R, v);
      if (R > m) cover(k << 1 | 1, m + 1, r, L, R, v);
      up(k);
    }
    int ask(int k, int l, int r, int L, int R) {
      if (l >= L && r <= R) return t[k];
      if (ad[k] != 0) down(k);
      int m = l + r >> 1, res = 1e9 + 7;
      if (L <= m) res = min(res, ask(k << 1, l, m, L, R));
      if (R > m) res = min(res, ask(k << 1 | 1, m + 1, r, L, R));
      return res;
    }
  } T;
  vector<pair<int, pair<int, int> > > L;
  inline void solve() {
    int ans = 1e9 + 7;
    cin >> n >> m;
    for (auto i = (1); i <= (n); ++i) {
      int l, r, w;
      cin >> l >> r >> w;
      L.push_back({w, {l, r - 1}});
    }
    --m;
    sort(L.begin(), L.end());
    T.build(1, 1, m);
    int r = -1;
    for (auto i = (1); i <= (n); ++i) {
      while (r < n - 1 && T.t[1] == 0)
        ++r, T.cover(1, 1, m, L[r].second.first, L[r].second.second, 1);
      if (T.t[1] > 0) ans = min(ans, L[r].first - L[i - 1].first);
      T.cover(1, 1, m, L[i - 1].second.first, L[i - 1].second.second, -1);
    }
    cout << ans << endl;
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while (T--) solve();
  }
  