# -*- coding: utf-8 -*-
import time
import re

fin = open("podatki.txt", "r")
m, n = map(int, re.split("\s+", fin.readline().strip()))
imenaKrajev = [fin.readline().strip() for i in range(m)]
d = [[0 for j in range(m)] for i in range(m)]

for i in range(1, m):
    for x, j in zip(map(int, re.split("\s+", fin.readline().strip())), range(i)):
        d[i][j] = d[j][i] = x

def najmanjseVpetoDrevo():
    # Kruskalov algoritem
    e = []
    for i in range(n-1):
        for j in range(i+1, n):
            e.append((d[i][j], i, j))
    e.sort()
    chosen = []
    barva = [i for i in range(n)]
    for l, u, v in e:
        if barva[u] == barva[v]: continue # nastal bi cikel
        staraBarva = barva[v]
        for i in range(n):
            if barva[i] == staraBarva:
                barva[i] = barva[u]
        chosen.append((u, v))
    return chosen

def eulerjevObhod(n, povezave):
    graf = [[] for i in range(n)]
    for u, v in povezave:
        graf[u].append(v)
        graf[v].append(u)
    obhod = []
    pomozni = [0]
    while len(pomozni) > 0:
        if len(graf[pomozni[-1]]) == 0:
            obhod.append(pomozni[-1])
            del pomozni[-1]
            continue
        u = pomozni[-1]
        v = graf[u][-1]
        del graf[u][-1]
        del graf[v][graf[v].index(u)]
        pomozni.append(v)
    return obhod

def lepCas(sekunde):
    if sekunde < 10:
        return "%.3f s" % sekunde
    elif round(sekunde) < 60:
        return "%.1f s" % sekunde
    else:
        sekunde = round(sekunde)
        minute = sekunde // 60
        sekunde %= 60
        return "%d min" % minute + (" %d s" % sekunde if sekunde > 0 else "")

start = time.time()
mst = najmanjseVpetoDrevo()
mst.extend(mst) # podvoji vse povezave
euler = eulerjevObhod(n, mst)
resitev = []
for x in euler:
    if x in resitev: continue
    resitev.append(x)
najkrajsa = sum(d[resitev[i]][resitev[i+1]] for i in range(n-1))
najkrajsa += d[resitev[0]][resitev[-1]]
stop = time.time()

print("cas racunanja:", lepCas(stop-start))
print("skupna razdalja:", najkrajsa)
resitev.append(resitev[0])
print(" --> ".join(imenaKrajev[x] for x in resitev))