Maco és el tipus de persona que diu que no li fa falta gps, va veure un documental de constel·lacions i diu que ell ja s'apanya. Òbviament, s'ha 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. Ajuda al pobre Maco a arribar a casa pel camí més curt possible.

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, es dirà quina llista necessita i el poble origen i destí.

Compte, els camins són bidireccionals.

Sortida

Hauràs de dir els km mínims que el Maco haurà de caminar per a arribar a casa. 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

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

106