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

infty = 10**20

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

najkrajsa = infty
resitev = None

used = [True] + [False for i in range(n-1)]
l = [0]

def greedy():
    global resitev
    global najkrajsa
    used = [True] + [False for i in range(n-1)]
    resitev = [0]
    for i in range(n-1):
        naslednja = None
        for j in range(n):
            if used[j]: continue
            if naslednja is None or d[resitev[-1]][j] < d[resitev[-1]][naslednja]:
                naslednja = j
        used[naslednja] = True
        resitev.append(naslednja)
    najkrajsa = d[resitev[0]][resitev[-1]]
    for i in range(n-1):
        najkrajsa += d[resitev[i]][resitev[i+1]]

def isci(level, dolzina):
    global najkrajsa
    global resitev
    if dolzina > najkrajsa:
        return # nima smisla
    if level == n:
        dolzina += d[l[0]][l[-1]]
        if dolzina < najkrajsa:
            najkrajsa = dolzina
            resitev = l[:]
        return
    for i in range(n):
        if used[i]: continue
        used[i] = True
        l.append(i)
        dolzina2 = dolzina + d[l[-1]][l[-2]]
        isci(level+1, dolzina2)
        del l[-1]
        used[i] = False

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()
greedy()
isci(1, 0)
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))