#https://i...content-available-to-author-only...e.com/54GWZA
 
#pocitame najmensie vzdialenosti z jedneho vrchola do vsetkych
#
#n, m - pocet vrcholov a hran; vrcholy pismena od 'A'
#v1 v2 vzd - 2 vrcholy a vzdialenost medzi nimi pre kazdu hranu
#v - pociatocny vrchol
 
import queue
 
n, m = [int(_) for _ in input().split()]
susedia = {}
vzdialenosti = {}
for x in range(n):
	susedia[chr(ord('A')+x)] = [] # x-te pismeno v poradi
	vzdialenosti[chr(ord('A')+x)] = float('inf') #nekonecno
print(susedia)
print(vzdialenosti)
for i in range(m):
	v1,v2,vzd = [_ for _ in input().split()]
	vzd = int(vzd)
	susedia[v1].append( (vzd, v2) )
	susedia[v2].append( (vzd, v1) )
v = input()
 
print(n, m)
print(v)
for s in susedia:
	print(s, susedia[s])
#pocitanie najkratsej cesty
mesta = queue.PriorityQueue() #prioritny rad pre mesta a ich vzdialenosti od pociatku
 
mesta.put( (0, v) ) #do vrcholu v sa vieme dostat cestou dlzky 0
while not mesta.empty():
	vzd, m = mesta.get() #
	if vzd < vzdialenosti[m]: #nasli sme kratsiu cestu
		vzdialenosti[m] = vzd #zapiseme ju
		for h in susedia[m]: #hrany k susedom
			c, v = h #c = vzdialenost z m do v
			mesta.put( (c+vzd, v) )
print(vzdialenosti)
 
 

I2h0dHBzOi8vaS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZS5jb20vNTRHV1pBCgojcG9jaXRhbWUgbmFqbWVuc2llIHZ6ZGlhbGVub3N0aSB6IGplZG5laG8gdnJjaG9sYSBkbyB2c2V0a3ljaAojCiNuLCBtIC0gcG9jZXQgdnJjaG9sb3YgYSBocmFuOyB2cmNob2x5IHBpc21lbmEgb2QgJ0EnCiN2MSB2MiB2emQgLSAyIHZyY2hvbHkgYSB2emRpYWxlbm9zdCBtZWR6aSBuaW1pIHByZSBrYXpkdSBocmFudQojdiAtIHBvY2lhdG9jbnkgdnJjaG9sCgppbXBvcnQgcXVldWUKCm4sIG0gPSBbaW50KF8pIGZvciBfIGluIGlucHV0KCkuc3BsaXQoKV0Kc3VzZWRpYSA9IHt9CnZ6ZGlhbGVub3N0aSA9IHt9CmZvciB4IGluIHJhbmdlKG4pOgoJc3VzZWRpYVtjaHIob3JkKCdBJykreCldID0gW10gIyB4LXRlIHBpc21lbm8gdiBwb3JhZGkKCXZ6ZGlhbGVub3N0aVtjaHIob3JkKCdBJykreCldID0gZmxvYXQoJ2luZicpICNuZWtvbmVjbm8KcHJpbnQoc3VzZWRpYSkKcHJpbnQodnpkaWFsZW5vc3RpKQpmb3IgaSBpbiByYW5nZShtKToKCXYxLHYyLHZ6ZCA9IFtfIGZvciBfIGluIGlucHV0KCkuc3BsaXQoKV0KCXZ6ZCA9IGludCh2emQpCglzdXNlZGlhW3YxXS5hcHBlbmQoICh2emQsIHYyKSApCglzdXNlZGlhW3YyXS5hcHBlbmQoICh2emQsIHYxKSApCnYgPSBpbnB1dCgpCgpwcmludChuLCBtKQpwcmludCh2KQpmb3IgcyBpbiBzdXNlZGlhOgoJcHJpbnQocywgc3VzZWRpYVtzXSkKI3BvY2l0YW5pZSBuYWprcmF0c2VqIGNlc3R5Cm1lc3RhID0gcXVldWUuUHJpb3JpdHlRdWV1ZSgpICNwcmlvcml0bnkgcmFkIHByZSBtZXN0YSBhIGljaCB2emRpYWxlbm9zdGkgb2QgcG9jaWF0a3UKCm1lc3RhLnB1dCggKDAsIHYpICkgI2RvIHZyY2hvbHUgdiBzYSB2aWVtZSBkb3N0YXQgY2VzdG91IGRsemt5IDAKd2hpbGUgbm90IG1lc3RhLmVtcHR5KCk6Cgl2emQsIG0gPSBtZXN0YS5nZXQoKSAjCglpZiB2emQgPCB2emRpYWxlbm9zdGlbbV06ICNuYXNsaSBzbWUga3JhdHNpdSBjZXN0dQoJCXZ6ZGlhbGVub3N0aVttXSA9IHZ6ZCAjemFwaXNlbWUganUKCQlmb3IgaCBpbiBzdXNlZGlhW21dOiAjaHJhbnkgayBzdXNlZG9tCgkJCWMsIHYgPSBoICNjID0gdnpkaWFsZW5vc3QgeiBtIGRvIHYKCQkJbWVzdGEucHV0KCAoYyt2emQsIHYpICkKcHJpbnQodnpkaWFsZW5vc3RpKQoJCQkKCQ==

NyAxMQpBIEIgNwpBIEQgNQpCIEMgOApCIEQgOQpCIEUgNwpDIEUgNQpEIEUgMTUKRCBGIDYKRSBGIDgKRSBHIDkKRiBHIDExCkQ=

7 11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11
D