(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(declaim (inline split-ints-into-vector))
(defun split-ints-into-vector (string dest-vector &key (offset 0) (key #'identity))
  (declare (string string)
           ((simple-array * (*)) dest-vector)
           ((integer 0 #.most-positive-fixnum) offset))
  (loop for idx from offset below (length dest-vector)
        for pos1 = 0 then (1+ pos2)
        for pos2 = (position #\space string :start pos1 :test #'char=)
        do (setf (aref dest-vector idx)
                 (funcall key (parse-integer string :start pos1 :end pos2)))
        finally (return dest-vector)))

(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
  "Note that the returned string will be reused."
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let ((,buffer (load-time-value (make-string ,buffer-size
                                                  :element-type 'base-char))))
       (declare (simple-base-string ,buffer))
       (loop for ,character of-type base-char =
                #-swank (code-char (read-byte ,in nil #\Newline))
                #+swank (read-char ,in nil #\Newline)
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (setf (schar ,buffer ,idx) ,terminate-char)
                     (return (values ,buffer ,idx))))))

(defmacro split-ints-and-bind (vars string &body body)
  (let ((pos1 (gensym "POS"))
	(pos2 (gensym "POS"))
	(str (gensym "STR")))
    (labels ((expand (vars &optional (init-pos1 t))
	       (if (null vars)
		   body
		   `((let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
			    (,pos2 (position #\space ,str :start ,pos1 :test #'char=))
			    (,(car vars) (parse-integer ,str :start ,pos1 :end ,pos2)))
		       ,@(expand (cdr vars) nil))))))
      `(let ((,str ,string))
         (declare (string ,str))
	 ,@(expand vars)))))


(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

;; Hauptteil
(declaim (inline map-permutations!))
(defun map-permutations! (function vector &optional (start 0) end)
  (declare (vector vector)
           (function function))
  (labels ((recurse (start end)
             (declare ((integer 0 #.most-positive-fixnum) start end))
             (if (> start end)
                 (funcall function vector)
                 (progn
                   (recurse (1+ start) end)
                   (loop for i from (1+ start) below end
                         do (rotatef (aref vector start) (aref vector i))
                            (recurse (1+ start) end)
                            (rotatef (aref vector start) (aref vector i)))))))
    (recurse start (or end (length vector)))))

(defmacro do-permutations! ((var vector &optional (start 0) end) &body body)
  `(map-permutations! (lambda (,var) ,@body) ,vector ,start ,end))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (m (read))
         (r (read))
         (rs (make-array r :element-type 'uint8))
         (mat (make-array (list n n) :element-type 'uint32 :initial-element #xffffffff)))
    (declare (uint32 n m r))
    (split-ints-into-vector (read-line) rs :key #'1-)
    (dotimes (i n)
      (setf (aref mat i i) 0))
    (dotimes (i m)
      (split-ints-and-bind (a b cost) (buffered-read-line 20)
        (declare (uint32 a b))
        (setf (aref mat (- a 1) (- b 1)) cost
              (aref mat (- b 1) (- a 1)) cost)))
    (dotimes (k n)
      (dotimes (i n)
        (do ((j (1+ i) (1+ j)))
            ((= j n))
          (when (> (aref mat i j) (+ (aref mat i k) (aref mat k j)))
            (setf (aref mat i j) (+ (aref mat i k) (aref mat k j))
                  (aref mat j i) (aref mat i j))))))
    (let ((min-cost #xffffffff))
      (do-permutations! (path rs)
        (let ((cost (loop for idx below (- r 1)
                          sum (aref mat (aref path idx) (aref path (1+ idx)))
                          of-type uint32)))
          (when (< cost min-cost)
            (setf min-cost cost))))
      (println min-cost))))

#-swank(main)


Measured memory_bytes: 26088