module WeightedDirectedGraph
  (Weight : sig
    type t
    val inf : t (* オーバーフローの恐れはないので，max_intとか突っ込んでも良い *)
    val zero : t
    val neg_inf : t (* オーバーフローの恐れはないので，min_intとか突っ込んでも良い *)
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  type 'a church_list = { fold : 'b. ('a -> 'b -> 'b) -> 'b -> 'b }

  val warshall_floyd :
    (* 頂点の数n *)
    int ->
    (* 辺のリスト *)
    (* 頂点は0からn-1までの整数でなくてはならない *)
    (int * int * Weight.t) church_list ->
    (* 辿り着けなければinf，負閉路を含む経路があればneg_infを返す関数 *)
    (int -> int -> Weight.t)
end =
struct
  type 'a church_list = { fold : 'b. ('a -> 'b -> 'b) -> 'b -> 'b }

  let warshall_floyd n es =
    let d = Array.make_matrix n n Weight.inf in
    for v = 0 to n - 1 do
      d.(v).(v) <- Weight.zero
    done;
    es.fold (fun (u, v, c) () ->
      (* c < d.(u).(v) *)
      if 0 < Weight.compare d.(u).(v) c
      then d.(u).(v) <- c) ();
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        for k = 0 to n - 1 do
          let open Weight in
          if 
            (* 経路がない場合は更新しない *)
            0 < Weight.compare inf d.(j).(i)
            && 0 < Weight.compare inf d.(i).(k)
            (* d.(j).(i) + d.(i).(k) < d.(j).(k) *)
            && 0 < Weight.compare d.(j).(k) (d.(j).(i) + d.(i).(k))
          then d.(j).(k) <- d.(j).(i) + d.(i).(k)
        done
      done
    done;
    for i = 0 to n - 1 do
      (* 頂点iを通る負閉路がある *)
      if 0 < Weight.compare Weight.zero d.(i).(i) then
        for j = 0 to n - 1 do
          for k = 0 to n - 1 do
            (* 負閉路を通る経路があれば，最短距離を負の無限大で更新 *)
            let open Weight in
            if 0 < Weight.compare inf d.(j).(i) && 0 < Weight.compare inf d.(i).(k)
            then d.(j).(k) <- Weight.neg_inf
          done
        done
    done;
    fun u v -> try d.(u).(v) with _ -> Weight.inf
end

module G = WeightedDirectedGraph (struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let inf = max_int
  let neg_inf = min_int
  let compare = compare
end)

let rec select acc trace = function
  | [] -> acc
  | x :: xs -> select ((trace, x, xs) :: acc) (x :: trace) xs
let select xs = select [] [] xs

let rec perm n xs =
  match n, xs with
  | 0, _ -> [[]]
  | _, [] -> []
  | n, xs ->
      List.concat @@
      List.map (fun (xs, x, ys) ->
        List.map (fun xs -> x :: xs) @@
        perm (n - 1) @@
        List.rev_append xs ys) @@
      select xs
(* 与えられたリストからn要素を選ぶ順列を列挙 *)
let perm : int -> 'a list -> 'a list list = fun n xs -> perm n @@ List.rev xs

let () = Scanf.scanf "%d %d %d\n" @@ fun n m r ->
  let rs = Array.init r @@ fun _ -> Scanf.scanf "%d " pred in
  let abcs = Array.init m @@ fun _ -> Scanf.scanf "%d %d %d\n" @@ fun a b c -> a - 1, b - 1, c in
  let d = G.warshall_floyd n { G.fold = fun f -> Array.fold_right (fun ((a, b, c) as e) acc -> f (b, a, c) @@ f e acc) abcs } in
  Printf.printf "%d\n" @@
  List.fold_left (fun acc (r :: rs) ->
    min acc @@
    snd @@
    List.fold_left (fun (r, a) s -> (s, d r s + a)) (r, 0) rs) max_int @@
  perm r @@
  Array.to_list rs
