[[問題文>練習問題#o006da2d]]
 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]