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 ar[300005];
  char ch[300005];
  int n, m, ii, k;
  namespace Segment_Tree {
  const int N = 1000005;
  int Tree[N * 4];
  int Lazy[N * 4];
  int vis[N * 4];
  void Relax(int node, int be, int en) {
    if (!vis[node]) return;
    Tree[node] += Lazy[node];
    if (be != en) {
      Lazy[node * 2] += Lazy[node];
      Lazy[node * 2 + 1] += Lazy[node];
      vis[node * 2] = 1;
      vis[node * 2 + 1] = 1;
    }
    Lazy[node] = 0;
    vis[node] = 0;
  }
  void Rupdate(int node, int be, int en, int i, int j, int val) {
    Relax(node, be, en);
    if (be > j || en < i) return;
    if (be >= i && en <= j) {
      Lazy[node] += val;
      vis[node] = 1;
      Relax(node, be, en);
      return;
    }
    int mid = (be + en) / 2;
    Rupdate(node * 2, be, mid, i, j, val);
    Rupdate(node * 2 + 1, mid + 1, en, i, j, val);
    Tree[node] = min(Tree[node * 2], Tree[node * 2 + 1]);
  }
  int query(int node, int be, int en, int i, int j) {
    Relax(node, be, en);
    if (be > j || en < i) return 1e9;
    if (be >= i && en <= j) return Tree[node];
    int mid = (be + en) / 2;
    return min(query(node * 2, be, mid, i, j),
               query(node * 2 + 1, mid + 1, en, i, j));
  }
  void dbg_test(int node, int be, int en) {
    if (be == en) return;
    int mid = (be + en) / 2;
    dbg_test(node * 2, be, mid);
    dbg_test(node * 2 + 1, mid + 1, en);
  }
  }  // namespace Segment_Tree
  using namespace Segment_Tree;
  vector<pair<int, pair<int, int>>> v;
  void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
      int x, y, w;
      scanf("%d%d%d", &x, &y, &w);
      v.push_back({w, {x, y}});
    }
    sort(v.begin(), v.end());
    int be = 0, en = 0;
    int re = 1e9;
    while (en < n) {
      int last = v[en].second.second;
      if (last != m) last--;
      Rupdate(1, 1, m, v[en].second.first, last, 1);
      int val = v[en].first;
      while (be <= en) {
        int va = query(1, 1, m, 1, m);
        if (va > 0) {
          re = min(re, val - v[be].first);
          last = v[be].second.second;
          if (last != m) last--;
          Rupdate(1, 1, m, v[be].second.first, last, -1);
          be++;
        } else
          break;
      }
      en++;
    }
    printf("%d\n", re);
  }
  int main() {
    int t = 1;
    while (t--) solve();
    return 0;
  }
  