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: import java.util.*;
  import java.io.*;
  
  public class BoringSegments {
      static int m;
      public static void main(String[] args) {
          FastScanner scanner = new FastScanner();
          PrintWriter out = new PrintWriter(System.out,false);
          int n = scanner.nextInt();
          m = scanner.nextInt();
          Seg[] segs = new Seg[n];
          for(int i = 0; i < n; i++) {
              segs[i] = new Seg(scanner.nextInt()-1, scanner.nextInt()-2, scanner.nextInt());
          }
          Arrays.sort(segs, new Comparator<Seg>() {
              public int compare(Seg o1, Seg o2) {
                  return o1.w - o2.w;
              }
          });
          out.println(comp(segs));
          out.flush();
      }
      static int comp(Seg[] segs) {
          int l = 0;
          SegTree sg = new SegTree(m-1, 0, m-2);
          int ans = 10000006;
          for(int i = 0; i < segs.length; i++) {
              //System.out.println("Adding: " + segs[i].l + " " + segs[i].r + " " + segs[i].w);
              sg.update(1,segs[i].l, segs[i].r, 1);
              while(sg.minimum(1,0, m-2) > 0) {
                  ans = Math.min(ans, segs[i].w-segs[l].w);
                  //System.out.println("Removing: " + segs[l].l + " " + segs[l].r + " " + segs[l].w);
                  sg.update(1,segs[l].l, segs[l].r, -1);
                  l++;
              }
          }
          return ans;
      }
      static class SegTree {
          int[] hi, lo, min, delta;
          public SegTree(int ss, int l, int r) {
              hi = new int[4 * ss + 1];
              lo = new int[4 * ss + 1];
              delta = new int[4 * ss + 1];
              min = new int[4 * ss + 1];
              init(1, l, r);
          }
          void init(int cur, int l, int r) {
              hi[cur] = r;
              lo[cur] = l;
              int mid = ( l + r)/2;
              if ( l == r) return;
              init(cur * 2, l, mid);
              init(cur * 2 + 1, mid + 1, r);
          }
          void prop(int cur) {
              delta[cur * 2] += delta[cur];
              delta[cur*2 + 1] += delta[cur];
              delta[cur] = 0;
          }
          void update(int cur) {
              min[cur] = Math.min(min[cur*2] + delta[cur * 2], min[cur * 2 + 1] + delta[cur*2 + 1]);
          }
          void update(int cur, int l, int r, int amt) {
              if (hi[cur] < l || lo[cur] > r) return;
              if (hi[cur] <= r && lo[cur] >= l) {
                  delta[cur] += amt;
                  return;
              }
              prop(cur);
              update(cur * 2, l, r, amt);
              update(cur*2 +1, l, r, amt);
              update(cur);
          }
          int minimum(int cur, int l, int r) {
              if (hi[cur] < l || lo[cur] > r) return Integer.MAX_VALUE;
              if (hi[cur] <= r && lo[cur] >= l) {
                  return min[cur] + delta[cur];
              }
              prop(cur);
              int lmin = minimum(cur * 2, l, r);
              int rmin = minimum(cur * 2 + 1, l, r);
              update(cur);
              return Math.min(lmin, rmin);
          }
      }
      static class Seg {
          int l,r,w;
          public Seg(int ll, int rr, int ww) {
              l = ll; r = rr; w =ww;
          }
      }
      public static class FastScanner {
          BufferedReader br;
          StringTokenizer st;
          public FastScanner(Reader in) {
              br = new BufferedReader(in);
          }
          public FastScanner() {
              this(new InputStreamReader(System.in));
          }
          String next() {
              while (st == null || !st.hasMoreElements()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
          int nextInt() {
              return Integer.parseInt(next());
          }
          long nextLong() {
              return Long.parseLong(next());
          }
          double nextDouble() {
              return Double.parseDouble(next());
          }
          String readNextLine() {
              String str = "";
              try {
                  str = br.readLine();
              } catch (IOException e) {
                  e.printStackTrace();
              }
              return str;
          }
      }
  }
  