import Data.Map ((!))
import qualified Data.Map 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 = result . foldl move (M.singleton (1,c) 0) . sort
 where
  minimum' xs = if null xs then -1 else minimum xs
  result im = minimum' $ M.elems $ M.filterWithKey (\(n',_) _ -> n'==n) im 

move im [s,t,y,m] = M.unionWith min im $ M.filterWithKey (\(_,c') _ -> c'>=0) $
 M.mapKeys (\(n',c') -> (t,c'-y)) $ M.map (+m) $ M.filterWithKey (\(n',_) _ -> n'==s) im