Anteriorment Maco et va demanar ajuda per saber la distància que havia de recórrer per tornar a casa, però... se li va oblidar demanar-te la ruta. Encara és perdut i l'únic que porta a sobre són llistes de pobles amb les distàncies entre ells, una de les llistes és de la seva zona. Fes una llista amb la ruta més curta i els km a recórrer. Aquesta vegada la llista la donarem al seu amic Taco, que és a casa de Maco. Taco tampoc és molt espavilat, així que recorda donar-li la llista des de casa del Maco fins a on es troba en Maco.

Entrada

La primera línia indica el número de llistes que hi ha. Cada llista té el nom de la llista, el número de connexions entre pobles i les connexions. Les connexions consten de dos pobles concatenats amb " -> " seguit pels km que separen als pobles. Finalment, és dirà quina llista necessita i el poble origen i destí.

Compte, els camins són unidireccionals.

Sortida

Hauràs de donar la llista de nodes que van des de casa del Maco fins al lloc on està Maco mes els km. Si no hi ha un camí possible es dirà "NO HI HA CAMÍ"

Cas de entrada 1

1
alicante
5
almoradi -> rafal
100
almoradi -> mudamiento
20
rafal -> mudamiento
80
rafal -> benejuzar
10
mudamiento -> benejuzar
20
alicante
almoradi -> benejuzar

Cas de sortida 1

[benejuzar, mudamiento, almoradi] 40

Cas de entrada 2

2
alicante
4
almoradi -> rafal
102
almoradi -> mudamiento
40
rafal -> mudamiento
85
mudamiento -> benejuzar
21
nationImagi
5
pueblopaleta -> maco
12
pueblopaleta -> paozu
4
pueblopaleta -> hyrule
10
maco -> hyrule
8
hyrule -> paozu
3
alicante
rafal -> benejuzar

Cas de sortida 2

[benejuzar, mudamiento, rafal] 106