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;
  template <typename A, typename B>
  ostream &operator<<(ostream &os, const pair<A, B> &p) {
    return os << '(' << p.first << ", " << p.second << ')';
  }
  template <typename T_container, typename T = typename enable_if<
                                      !is_same<T_container, string>::value,
                                      typename T_container::value_type>::type>
  ostream &operator<<(ostream &os, const T_container &v) {
    os << '{';
    string sep;
    for (const T &x : v) os << sep << x, sep = ", ";
    return os << '}';
  }
  void dbg_out() { cerr << '\n'; }
  template <typename Head, typename... Tail>
  void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
  }
  const long long int inf = 9e18;
  class ST {
   public:
    long long int leftmost, rightmost, to_prop, val;
    ST *lchild, *rchild;
    ST(long long int l, long long int r) {
      leftmost = l;
      rightmost = r;
      val = to_prop = 0;
      lchild = rchild = nullptr;
      if (l != r) {
        long long int mid = (l + r) / 2;
        lchild = new ST(l, mid);
        rchild = new ST(mid + 1, r);
      }
    }
    void recal() {
      if (lchild) {
        val = min(lchild->get_val(), rchild->get_val());
      }
    }
    void prop() {
      if (lchild) {
        lchild->to_prop += to_prop;
        rchild->to_prop += to_prop;
        to_prop = 0;
      }
      recal();
    }
    long long int get_val() { return val + to_prop; }
    void addRange(long long int l, long long int r, long long int v) {
      if (l > rightmost or r < leftmost) return;
      if (l <= leftmost and r >= rightmost) {
        to_prop += v;
        return;
      }
      lchild->addRange(l, r, v);
      rchild->addRange(l, r, v);
      recal();
    }
    long long int query(long long int l, long long int r) {
      if (l > rightmost or r < leftmost) return inf;
      if (l <= leftmost and r >= rightmost) {
        return get_val();
      }
      prop();
      long long int lf = lchild->query(l, r);
      long long int rf = rchild->query(l, r);
      return min(lf, rf);
    }
  };
  int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long int n, m;
    cin >> n >> m;
    vector<tuple<long long int, long long int, long long int> > in;
    long long int l, r, w;
    for (long long int i = 1; i <= n; i++) {
      cin >> l >> r >> w;
      in.emplace_back(w, 2 * (l - 1), 2 * (r - 1));
    }
    sort(in.begin(), in.end());
    m--;
    ST st(0, 2 * m);
    l = 0;
    r = -1;
    long long int ans = inf;
    while (l < n) {
      while (r + 1 < n and st.get_val() == 0) {
        r++;
        auto [w, u, v] = in[r];
        st.addRange(u, v, 1);
      }
      if (st.get_val() != 0) ans = min(ans, get<0>(in[r]) - get<0>(in[l]));
      st.addRange(get<1>(in[l]), get<2>(in[l]), -1);
      l++;
    }
    cout << ans << '\n';
    return 0;
  }
  