ans={}
import numpy as np 
b=list(input().split(','))
for i in range(len(b)):
  ans[b[i]]= ['NIL',np.inf]
n = int(input())
w=[]
for i in range(n):
  w.append(list(input().split(',')))
ans['A'] = ['NIL',0]
adj={}
for i in range(len(w)):
  adj[w[i][0]]=[]
for i in range(len(w)): 
  adj[w[i][0]].append(w[i][1])
S=[]
ans
def relax(u,v,w):
  W=0
  for i in range(len(w)):
    if w[i][0] == u and w[i][1] == v:
      W= int(w[i][2])
  if ans[v][1] > ans[u][1] + W:
    ans[v][1] = ans[u][1] + W
    ans[v][0] = u
for i in range(len(b)) :
  u= sorted(ans.items(),key = lambda item: item[1][1])[i][0]
  S.append(u)
  for i in range(len(b)):
    if b[i] in adj[u]:
      relax(u,b[i],w)
for i in range(len(b)):
  print(ans[b[i]][1])

YW5zPXt9CmltcG9ydCBudW1weSBhcyBucCAKYj1saXN0KGlucHV0KCkuc3BsaXQoJywnKSkKZm9yIGkgaW4gcmFuZ2UobGVuKGIpKToKICBhbnNbYltpXV09IFsnTklMJyxucC5pbmZdCm4gPSBpbnQoaW5wdXQoKSkKdz1bXQpmb3IgaSBpbiByYW5nZShuKToKICB3LmFwcGVuZChsaXN0KGlucHV0KCkuc3BsaXQoJywnKSkpCmFuc1snQSddID0gWydOSUwnLDBdCmFkaj17fQpmb3IgaSBpbiByYW5nZShsZW4odykpOgogIGFkalt3W2ldWzBdXT1bXQpmb3IgaSBpbiByYW5nZShsZW4odykpOiAKICBhZGpbd1tpXVswXV0uYXBwZW5kKHdbaV1bMV0pClM9W10KYW5zCmRlZiByZWxheCh1LHYsdyk6CiAgVz0wCiAgZm9yIGkgaW4gcmFuZ2UobGVuKHcpKToKICAgIGlmIHdbaV1bMF0gPT0gdSBhbmQgd1tpXVsxXSA9PSB2OgogICAgICBXPSBpbnQod1tpXVsyXSkKICBpZiBhbnNbdl1bMV0gPiBhbnNbdV1bMV0gKyBXOgogICAgYW5zW3ZdWzFdID0gYW5zW3VdWzFdICsgVwogICAgYW5zW3ZdWzBdID0gdQpmb3IgaSBpbiByYW5nZShsZW4oYikpIDoKICB1PSBzb3J0ZWQoYW5zLml0ZW1zKCksa2V5ID0gbGFtYmRhIGl0ZW06IGl0ZW1bMV1bMV0pW2ldWzBdCiAgUy5hcHBlbmQodSkKICBmb3IgaSBpbiByYW5nZShsZW4oYikpOgogICAgaWYgYltpXSBpbiBhZGpbdV06CiAgICAgIHJlbGF4KHUsYltpXSx3KQpmb3IgaSBpbiByYW5nZShsZW4oYikpOgogIHByaW50KGFuc1tiW2ldXVsxXSk=

QSxCLEMsRCxFLEYsRyxILEksSixLCjYyCkEsQiw1CkEsQyw3CkEsRCw2CkEsRiwzCkEsRyw3CkEsSiwyCkEsSywyCkIsRCwyCkIsRSw1CkIsRiwxCkIsSSw2CkIsSiw2CkIsSyw0CkMsRSw1CkMsRiwyCkMsSCw1CkMsSSwyCkMsSiw2CkQsQSw1CkQsQiw1CkQsQyw0CkQsRSw2CkQsRiwzCkQsSSw0CkUsQSwyCkUsQyw0CkUsRCw0CkUsRiw2CkUsSCw1CkUsSSwyCkYsQiwyCkYsSSw3CkYsSyw3CkcsQiw3CkcsQyw3CkcsRiw2CkcsSiwxCkcsSyw1CkgsQSw3CkgsRSwzCkgsRywyCkgsSSw0CkgsSiwzCkgsSyw1CkksQSwyCkksQiw3CkksRiw2CkksRyw1CkksSyw2CkosQSw2CkosQyw1CkosRCwzCkosRSw1CkosRyw0CkssQSw1CkssQiwzCkssQyw1CkssRCw1CkssRSw2CkssRywzCkssSCw3CkssSiw3

A,B,C,D,E,F,G,H,I,J,K
62
A,B,5
A,C,7
A,D,6
A,F,3
A,G,7
A,J,2
A,K,2
B,D,2
B,E,5
B,F,1
B,I,6
B,J,6
B,K,4
C,E,5
C,F,2
C,H,5
C,I,2
C,J,6
D,A,5
D,B,5
D,C,4
D,E,6
D,F,3
D,I,4
E,A,2
E,C,4
E,D,4
E,F,6
E,H,5
E,I,2
F,B,2
F,I,7
F,K,7
G,B,7
G,C,7
G,F,6
G,J,1
G,K,5
H,A,7
H,E,3
H,G,2
H,I,4
H,J,3
H,K,5
I,A,2
I,B,7
I,F,6
I,G,5
I,K,6
J,A,6
J,C,5
J,D,3
J,E,5
J,G,4
K,A,5
K,B,3
K,C,5
K,D,5
K,E,6
K,G,3
K,H,7
K,J,7