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.io.*;
  import java.util.*;
  
  public class Codeforces
  {
      public static void main(String args[])throws Exception
      {
          BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb=new StringBuilder();
          String s[]=bu.readLine().split(" ");
          int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
          st=new int[4*m]; l=new int[4*m];
  
          int i,j,a[][]=new int[n][3];
          PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {
              @Override
              public int compare(int[] o1, int[] o2) {
                  if(o1[2]>o2[2]) return 1;
                  else return -1;
              }});
          for(i=0;i<n;i++)
          {
              s=bu.readLine().split(" ");
              for(j=0;j<3;j++) a[i][j]=Integer.parseInt(s[j]);
              a[i][0]--; a[i][1]-=2;
              pq.add(a[i]);
          }
  
          int l=0,ans=Integer.MAX_VALUE;
          for(i=0;i<n;i++)
          {
              a[i]=pq.poll();
              update(0,m-1,a[i][0],a[i][1],1,0);
              while(l<i && query(0,m-1,0,m-2,0)>0)
              {
                  ans=Math.min(ans,a[i][2]-a[l][2]);
                  update(0,m-1,a[l][0],a[l][1],-1,0);
                  l++;
              }
              if(query(0,m-1,0,m-2,0)>0) ans=Math.min(ans,a[i][2]-a[l][2]);
          }
          System.out.print(ans);
      }
  
      static int l[],st[];
      static void update(int ss,int se,int us,int ue,int v,int n)
      {
          if(l[n]!=0)
          {
              st[n]+=l[n];
              if(ss!=se) {l[2*n+1]+=l[n]; l[2*n+2]+=l[n];}
              l[n]=0;
          }
  
          if(ss>se || ss>ue || se<us) return;
          if(us<=ss && ue>=se)
          {
              st[n]+=v;
              if(ss!=se) {l[2*n+1]+=v; l[2*n+2]+=v;}
              return;
          }
  
          int m=(ss+se)/2;
          update(ss,m,us,ue,v,2*n+1);
          update(m+1,se,us,ue,v,2*n+2);
          st[n]=Math.min(st[2*n+1],st[2*n+2]);
      }
  
      static int query(int ss,int se,int qs,int qe,int n)
      {
          if(l[n]!=0)
          {
              st[n]+=l[n];
              if(ss!=se) {l[2*n+1]+=l[n]; l[2*n+2]+=l[n];}
              l[n]=0;
          }
  
          if(ss>se || ss>qe || se<qs) return Integer.MAX_VALUE;
          if(qs<=ss && qe>=se) return st[n];
  
          int m=(ss+se)/2;
          return Math.min(query(ss,m,qs,qe,2*n+1),query(m+1,se,qs,qe,2*n+2));
      }
  }
  