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>
  template <typename T>
  class SegmentTree {
   private:
    struct TreeNode {
      T value;
      T min_value;
      bool needs_push;
    };
    std::vector<TreeNode> data_;
    size_t size;
    void push(size_t i) {
      if (data_[i].needs_push) {
        data_[i * 2 + 1].value = data_[i].value;
        data_[i * 2 + 1].min_value = data_[i].value;
        data_[i * 2 + 1].needs_push = true;
        data_[i * 2 + 2].value = data_[i].value;
        data_[i * 2 + 2].min_value = data_[i].value;
        data_[i * 2 + 2].needs_push = true;
        data_[i].needs_push = false;
      }
    }
    void RangeUpdate(size_t i, size_t tree_left, size_t tree_right, size_t left,
                     size_t right, T value) {
      if (left >= tree_right || right <= tree_left) {
        return;
      } else if (left <= tree_left && right >= tree_right) {
        data_[i].value = value;
        data_[i].min_value = value;
        data_[i].needs_push = true;
      } else {
        push(i);
        size_t tree_mid = (tree_left + tree_right) / 2;
        RangeUpdate(i * 2 + 1, tree_left, tree_mid, left, right, value);
        RangeUpdate(i * 2 + 2, tree_mid, tree_right, left, right, value);
        data_[i].min_value =
            std::min(data_[i * 2 + 1].min_value, data_[i * 2 + 2].min_value);
      }
    }
    T RangeMin(size_t i, size_t tree_left, size_t tree_right, size_t left,
               size_t right) {
      if (left <= tree_left && right >= tree_right) {
        return data_[i].min_value;
      } else {
        push(i);
        size_t tree_mid = (tree_left + tree_right) / 2;
        if (tree_mid <= left) {
          return RangeMin(i * 2 + 2, tree_mid, tree_right, left, right);
        } else if (tree_mid >= right) {
          return RangeMin(i * 2 + 1, tree_left, tree_mid, left, right);
        } else {
          return std::min(RangeMin(i * 2 + 2, tree_mid, tree_right, left, right),
                          RangeMin(i * 2 + 1, tree_left, tree_mid, left, right));
        }
      }
    }
  
   public:
    SegmentTree(size_t size, T default_value) : size(size) {
      data_.resize(size * 4, TreeNode{default_value, default_value, false});
    }
    void Update(size_t left, size_t right, T value) {
      RangeUpdate(0, 0, size, left, right, value);
    }
    T GetMin(size_t left, size_t right) {
      return RangeMin(0, 0, size, left, right);
    }
  };
  void Solve() {
    int n = 0, m = 0, left = 0, right = 0, weight = 0;
    long long ans = 1e12, cur_min = 0;
    std::cin >> n >> m;
    std::vector<std::tuple<int, size_t, size_t>> segments;
    SegmentTree<int> tree(m * 2, -1);
    for (int i = 0; i < n; ++i) {
      std::cin >> left >> right >> weight;
      segments.emplace_back(weight, (left - 1) * 2, right * 2 - 1);
    }
    std::sort(segments.begin(), segments.end());
    for (const auto& segment : segments) {
      tree.Update(std::get<1>(segment), std::get<2>(segment),
                  std::get<0>(segment));
      cur_min = tree.GetMin(0, m * 2 - 1);
      if (cur_min > -1) {
        ans = std::min(ans, std::get<0>(segment) - cur_min);
      }
    }
    std::cout << ans << '\n';
  }
  int main() { Solve(); }
  