問題文

def dijk(s):
  global d, prev
  d = [0] * V
  used = [False] * V
  prev = [-1] * V
  d[s] = 0
  while 1:
    v = -1
    for u in xrange(V):
      if v!=-1 and cost[v][u] == INF: continue
      if not used[u] and (v==-1 or d[u] > d[v]): v = u
    if v == -1: break
    used[v] = True
    for u in xrange(V):
      if cost[v][u] == INF: continue
      if d[u] < d[v] + cost[v][u]:
        d[u] = d[v] + cost[v][u]
        prev[u] = v

def get_path(t):
  path = []
  while t != -1:
    path.append(chr(ord('A')+t))
    t = prev[t]
  return ' -> '.join(path[::-1])

V, E = map(int, raw_input().split())
INF = 987654321
cost = [ [ INF for _ in xrange(V+1) ] for _ in xrange(V+1) ]
for _ in xrange(E):
  a, b, c = raw_input().split()
  a = ord(a) - ord('A')
  b = ord(b) - ord('A') 
  cost[a][b] = int(c)
dijk(0)
print get_path(V-1)
print d[V-1]