(defun input (n)
  (let ((A (make-array n))
        (B (make-array n))
        (C (make-array n)))
    (loop for i below n
          do (progn (setf (aref A i) (1- (read)))
                    (setf (aref B i) (1- (read)))
                    (setf (aref C i) (1- (read)))))
    (values A B C)))

(defun w-f (n A)
  (dotimes (k n) (dotimes (i n) (dotimes (j n)
    (setf (aref A i j) (min (aref A i j) (+ (aref A i k) (aref A k j))))))))

(defun num-list (n)
  (loop for i below n collect i))

(defun solve (n m A B C)
  (let ((d (make-array '(100 100) :initial-element 3000000))
        (ans m))
    (dotimes (i m)
      (setf (aref d (aref A i) (aref B i)) (aref C i))
      (setf (aref d (aref B i) (aref A i)) (aref C i)))
    (dotimes (i n) (setf (aref d i i) 0))
    (w-f n d)
    (labels ((test (i)
               (= n 
                  (count-if
                    (lambda (j)
                      (if (= (+ (aref d j (aref A i)) (aref C i))
                             (aref d j (aref B i)))
                        t
                        nil))
                    (num-list n)))))
      (- m (count-if (lambda (i) (test i)) (num-list m))))))

(let ((n (read))
      (m (read)))
  (multiple-value-bind (A B C) (input m)
    (princ (solve n m A B C))))