Scanf.scanf "%d %d %d" (fun n m r ->
    let next_permutation list =
        let rec phase3 taddr = function
            | _  :: tl when tl == taddr -> []
            | hd :: tl                  -> hd :: phase3 taddr tl
            | []                        -> [] in

        let rec phase2 h2 taddr = function
            | h1 :: tl when h1 > h2 -> let lis = phase3 taddr tl in
                                       h1, h2 :: lis
            | h1 :: tl              -> let hh, lis = phase2 h2 taddr tl in
                                       hh, h1 :: lis
            | _                     -> failwith "??" in

        let rec phase1 list = function
            | h1 :: h2 :: tl when h1 > h2  -> let hh, lis = phase2 h2   tl list in
                                              List.rev_append tl (hh :: lis)
            | _  :: tl                     -> phase1 list tl
            | _                            -> list in

        let rev_list = List.rev list in
        phase1 rev_list rev_list
    in
    let ri = Array.init r (fun _ -> Scanf.scanf " %d" (fun r -> r - 1)) in
    let nei = Array.make n [] in
    for i = 1 to m do
        Scanf.scanf " %d %d %d" (fun a b c ->
            let a = a - 1 in
            let b = b - 1 in
            nei.(a) <- (c, b) :: nei.(a);
            nei.(b) <- (c, a) :: nei.(b);
        )
    done;
    let module S = Set.Make (struct type t = int * int let compare = compare end) in
    let dijkstra s g =
        let d = Array.make n max_int in
        d.(s) <- 0;
        let rec loop set =
            if S.is_empty set then () else
                let ((dd, cur) as m) = S.min_elt set in
                let set = S.remove m set in
                let set = List.fold_left (fun set (nc, nv) ->
                    if d.(nv) <= nc + dd then set else (
                        d.(nv) <- nc + dd;
                        S.add (nc + dd, nv) set
                    )
                ) set nei.(cur)
                in
                loop set
        in
        loop (S.singleton (0, s));
        d.(g)
    in
    let dist = Array.make_matrix r r max_int in
    for i = 0 to r - 1 do
        dist.(i).(i) <- 0;
        for j = i + 1 to r - 1 do
            let c = dijkstra ri.(i) ri.(j) in
            dist.(i).(j) <- c;
            dist.(j).(i) <- c;
        done
    done;
    let rec iota a = if a < 0 then [] else a :: iota (a - 1) in
    let rec fact a = if a = 0 then 1  else a *  fact (a - 1) in

    let calc l =
        match l with
        | [] -> 0
        | hd :: tl ->
                let rec loop prev sum = function
                    | [] -> sum
                    | x :: xs -> loop x (sum + dist.(prev).(x)) xs
                in
                loop hd 0 tl
    in

    let rec loop i lis acc =
        if i = 0 then acc else
            loop (i - 1) (next_permutation lis) (min acc (calc lis))
    in
    loop (fact r) (iota (r - 1)) max_int |> Printf.printf "%d\n"
)