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 ll = long long;
  using namespace std;
  int n, m;
  int const N = 3e5 + 2;
  int const M = (1 << 21);
  struct Triple {
    int fi;
    int se;
    int th;
    Triple(int f, int s, int t) : fi(f), se(s), th(t) {}
  };
  struct Compare {
    bool operator()(const Triple& f, const Triple& g) {
      if (f.th != g.th)
        return (f.th < g.th);
      else
        return pair<int, int>{f.fi, f.se} < pair<int, int>{g.fi, g.se};
    }
  };
  vector<Triple> seg;
  int t[M];
  int lazy[M];
  int const INF = 1e9;
  void push(int v) {
    t[v * 2] += lazy[v];
    lazy[v * 2] += lazy[v];
    t[v * 2 + 1] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
  }
  int query(int v, int l, int r, int tl, int tr) {
    if (r < l) return INF;
    if (l == tl && r == tr)
      return t[v];
    else {
      push(v);
      int mid = (tl + tr) / 2;
      int qw1 = query(v * 2, l, min(mid, r), tl, mid);
      int qw2 = query(v * 2 + 1, max(mid + 1, l), r, mid + 1, tr);
      return min(qw1, qw2);
    }
  }
  void update(int v, int l, int r, int tl, int tr, int val) {
    if (r < l) return;
    if (l == tl && r == tr) {
      t[v] += val;
      lazy[v] += val;
    } else {
      push(v);
      int mid = (tl + tr) >> 1;
      update(v << 1, l, min(mid, r), tl, mid, val);
      update((v << 1) + 1, max(mid + 1, l), r, mid + 1, tr, val);
      t[v] = min(t[v << 1], t[(v << 1) + 1]);
    }
  }
  int main() {
    scanf("%d %d", &n, &m);
    for (int i = (1); i <= (n); i++) {
      int l, r, w;
      scanf("%d %d %d", &l, &r, &w);
      seg.push_back(Triple({l, r, w}));
    }
    sort(seg.begin(), seg.end(), Compare());
    int mu = 0;
    int lb = seg[0].th;
    int rb = seg[0].th;
    int ans = INF;
    for (int i = (1); i <= (n); i++) {
      update(1, seg[i - 1].fi, seg[i - 1].se - 1, 1, m - 1, 1);
      rb = seg[i - 1].th;
      while (query(1, 1, m - 1, 1, m - 1) > 0) {
        ans = min(ans, rb - lb);
        update(1, seg[mu].fi, seg[mu].se - 1, 1, m - 1, -1);
        mu++;
        if (mu != n) lb = seg[mu].th;
      }
    }
    printf("%d", ans);
    return 0;
  }
  