import Data.IntMap ((!))
import qualified Data.IntMap as M
import Data.List

main = do
 n <- readLn
 c <- readLn
 getLine
 styms <- transpose . map (map read . words) . lines <$> getContents
 print (shortcut n c styms)

shortcut n c = snd . M.findWithDefault (-1,-1) n . foldl (move n) (M.singleton 1 (c,0)) . sort

move n im [s,t,y,m]
 | not (M.member s im) = im
 | y'-y < 0 = im
 | otherwise = M.insertWith eval t (y'-y,m'+m) im
 where
  (y',m') = im!s
  eval (y1,m1) (y2,m2)
   | m2 <= m1 = (y2,m2)
   | otherwise = (y1,m1)