(ns challenge-0152.core
  (:require [clojure.set :refer [union]]
            [clojure.java.io :refer [reader]]
            [clojure.string :refer [join]])
  (:gen-class))

(defn make-letter-range [num]
  (map char
       (take num
             (range (int \a)
                    (inc (int \z))))))

(defn process-node [line letter-range]
  (let [distances (re-seq #"[\d-]+" line)]
    (loop [distance (first distances)
           more-distances (next distances)
           node2 (first letter-range)
           more-nodes (next letter-range)
           result {}]
      (let [new-result (if (pos? (Integer. distance))
                         (conj result {node2 (Integer. distance)})
                         result)]
        (if more-distances
          (recur (first more-distances)
                 (next more-distances)
                 (first more-nodes)
                 (next more-nodes)
                 new-result)
          new-result)))))

(defn make-graph [matrix]
  (let [letter-range (make-letter-range (count matrix))]
    (loop [line (first matrix)
           more-lines (next matrix)
           node1 (first letter-range)
           more-nodes (next letter-range)
           result {}]
      (let [node-result {node1 (process-node line letter-range)}
            new-result (conj result node-result)]
        (if more-lines
          (recur (first more-lines)
                 (next more-lines)
                 (first more-nodes)
                 (rest more-nodes)
                 new-result)
          new-result)))))

(defn make-edge-map [map]
  (loop [vertice (first map)
         xs (next map)
         processed #{}
         result {}]
    (let [new-edges (for [edge (val vertice)
                          :when (not (contains? processed (key edge)))]
                      [[(key vertice) (key edge)] (val edge)])]
      (if xs
        (recur (first xs)
               (next xs)
               (conj processed (key vertice))
               (if (seq new-edges)
                 (into result new-edges)
                 result))
        (reduce conj result new-edges)))))

(defn minimal-spanning-tree [graph]
  (let [edge-map (make-edge-map graph)
        sorted-edge-map (into (sorted-map-by (fn [k1 k2]
                                               (compare [(edge-map k1) k1]
                                                        [(edge-map k2) k2])))
                              edge-map)]
    (loop [sets (apply conj (for [node (make-letter-range (count graph))]
                              {node #{node}}))
           result {}
           [[node1 node2] distance] (first sorted-edge-map)
           xs (next sorted-edge-map)]
      (if (= (sets node1) (sets node2))
        (if xs
          (recur sets result (first xs) (next xs))
          result)
        (let [new-result (conj result {(str node1 node2) distance})
              nodes-union (union (sets node1) (sets node2))
              new-sets (apply conj sets (for [node nodes-union]
                                          {node nodes-union}))]
          (if xs
            (recur new-sets new-result (first xs) (next xs))
            new-result))))))

(defn -main [& args]
  (with-open [input (reader *in*)]
    (let [mst (minimal-spanning-tree (make-graph (rest (line-seq input))))
          distance (reduce #(+ %1 (val %2)) 0 mst)]
      (println distance)
      (println (join " " (keys mst))))))

(-main)