#!/usr/bin/python
# -*- coding: utf-8 -*-

def form(d,i,fait,inf):
  if d=="@":
    return " - |"
  elif d==inf:
    return " ∞ |"
  c=str(d)
  if i not in fait:
    if len(c)==1:
      return " "+c+" |"
    return " "*(3-len(c))+c+"|"
  return " * |"

#M=[[0,12,0,14,0,0,0,0],
#   [12,0,0,0,0,9,16,21],
#   [0,0,0,0,13,10,0,0],
#   [14,0,0,0,10,0,0,0],
#   [0,0,13,10,0,16,0,10],
#   [0,9,10,0,16,0,0,11],
#   [0,16,0,0,0,0,0,11],
#   [0,21,0,0,10,11,11,0]]

#M=[[0,400,0,600,0,0,0,0],
#   [400,0,600,0,400,0,0,0],
#   [0,600,0,0,350,0,550,450],
#   [600,0,0,0,300,0,0,900],
#   [0,400,350,300,0,0,600,0],
#   [0,0,0,0,0,0,200,400],
#   [0,0,550,0,600,200,0,300],
#   [0,0,450,900,0,400,300,0]]

M=[[0,5,0,0,4,3,5],
   [5,0,5,1,1,0,0],
   [0,5,0,3,0,0,0],
   [0,1,3,0,0,0,0],
   [4,1,0,0,0,2,0],
   [3,0,0,0,2,0,3],
   [5,0,0,0,0,0,3]]

M=[[ 0, 5,25, 0, 0, 0, 0,10,15],
   [ 5, 0,30, 0, 0, 0, 0, 0, 0],
   [25,30, 0,20, 0, 0, 0, 0, 0],
   [ 0, 0,20, 0,20, 0, 0, 0,15],
   [ 0, 0, 0,20, 0,20, 0, 0,15],
   [ 0, 0, 0, 0,20, 0, 5,10, 0],
   [ 0, 0, 0, 0, 0, 5, 0,20, 0],
   [10, 0, 0, 0, 0,10,20, 0,20],
   [15, 0, 0,15,15, 0, 0,20, 0]]

M=[[0,6,5,2,0,0,0],
   [6,0,5,0,0,0,5],
   [5,5,0,2,0,0,4],
   [2,0,2,0,9,0,0],
   [0,0,0,9,0,4,2],
   [0,0,0,0,4,0,7],
   [0,5,4,0,2,7,0]]

inf=len(M)*(max(max(l) for l in M)+1)
precedent=[-1 for s in range(len(M))]
distances=[inf for s in range(len(M))]
depart=ord("A")-65
arrivee=ord("F")-65
distances[depart]=0
fait=set()
afaire=set(range(len(M)))

print(" "+" | ".join(chr(i+65) for i in range(len(M)))+" | choix")

while afaire:
  dmin=inf
  for s in afaire:
    if dmin>distances[s]:
      dmin=distances[s]
      smin=s
  print("-"*(4*len(M)+7))
  print("".join(form(distances[i],i,fait,inf) for i in range(len(M)))+" "*3+chr(smin+65))
  print("".join(form(chr(precedent[i]+65),i,fait,inf) for i in range(len(M)))+" préc.")
  fait.add(smin)
  afaire.remove(smin)
  for s in afaire:
    if distances[smin]+M[s][smin]<distances[s] and M[s][smin]:
      distances[s]=distances[smin]+M[s][smin]
      precedent[s]=smin

s=arrivee
pluscourt=[s]
while s!=depart:
  s=precedent[s]
  pluscourt=[s]+pluscourt

print(distances[arrivee])
print("-".join([chr(i+65) for i in pluscourt]))