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: from sys import stdin, stdout
  
  class LazySegmentTree:
      def __init__(self, data, default=0, func=min):
          """initialize the lazy segment tree with data"""
          self._default = default
          self._func = func
  
          self._len = len(data)
          self._size = _size = 1 << (self._len - 1).bit_length()
          self._lazy = [0] * (2 * _size)
  
          self.data = [default] * (2 * _size)
          self.data[_size:_size + self._len] = data
          for i in reversed(range(_size)):
              self.data[i] = func(self.data[i + i], self.data[i + i + 1])
  
      def __len__(self):
          return self._len
  
      def _push(self, idx):
          """push query on idx to its children"""
          # Let the children know of the queries
          q, self._lazy[idx] = self._lazy[idx], 0
  
          self._lazy[2 * idx] += q
          self._lazy[2 * idx + 1] += q
          self.data[2 * idx] += q
          self.data[2 * idx + 1] += q
  
      def _update(self, idx):
          """updates the node idx to know of all queries applied to it via its ancestors"""
          for i in reversed(range(1, idx.bit_length())):
              self._push(idx >> i)
  
      def _build(self, idx):
          """make the changes to idx be known to its ancestors"""
          idx >>= 1
          while idx:
              self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1]) + self._lazy[idx]
              idx >>= 1
  
      def add(self, start, stop, value):
          """lazily add value to [start, stop)"""
          start = start_copy = start + self._size
          stop = stop_copy = stop + self._size
          while start < stop:
              if start & 1:
                  self._lazy[start] += value
                  self.data[start] += value
                  start += 1
              if stop & 1:
                  stop -= 1
                  self._lazy[stop] += value
                  self.data[stop] += value
              start >>= 1
              stop >>= 1
  
          # Tell all nodes above of the updated area of the updates
          self._build(start_copy)
          self._build(stop_copy - 1)
  
      def query(self, start, stop, default=1e10):
          """func of data[start, stop)"""
          start += self._size
          stop += self._size
  
          # Apply all the lazily stored queries
          self._update(start)
          self._update(stop - 1)
  
          res = default
          while start < stop:
              if start & 1:
                  res = self._func(res, self.data[start])
                  start += 1
              if stop & 1:
                  stop -= 1
                  res = self._func(res, self.data[stop])
              start >>= 1
              stop >>= 1
          return res
  
      def __repr__(self):
          return "LazySegmentTree({0})".format(self.data)
  
  n, m = [int(x) for x in stdin.readline().split()]
  
  segments = []
  for i in range(n):
      segments.append([int(x) for x in stdin.readline().split()])
  segments.sort(key = lambda x:x[2])
  
  answer = 1000001
  
  tree = LazySegmentTree([0]*(m-1))
  i = 0
  j = 0
  while i < n:
      while j < n:
          tree.add(segments[j][0]-1, segments[j][1]-1, 1)
          if tree.query(0,m-1):
              answer = min(answer, segments[j][2]-segments[i][2])
              break
          else:
              j += 1
      tree.add(segments[i][0]-1, segments[i][1]-1, -1)
      i += 1
      while tree.query(0,m-1):
          answer = min(answer, segments[j][2]-segments[i][2])
          tree.add(segments[i][0]-1, segments[i][1]-1, -1)
          i += 1
      j += 1
  
  stdout.write(str(answer) + '\n')
  