Byteasar has become a hexer - a conqueror of monsters. Currently he is to return to his hometown Byt
eburg. The way home, alas, leads through a land full of beasts. Fortunately the habitants, forced to
fight the monsters for centuries, have mastered the art of blacksmithery - they are now capable ofma
king special swords that are very efficient against the beasts. The land Byteasar wanders throughis
quite vast: many towns lie there, and many roads connect them. These roads do not cross outside the
towns (mostly because some of them are underground passages).Byteasar has gathered all practicalinfo
rmation about the land (all hexers like to know these things). He knows what kind of monsters hemay
come across each of the roads and how much time he needs to walk it down. He also knows in which vil
lages there are blacksmiths and against what kinds of monsters the swords that they make work.Byteas
ar wants to get back to Byteburg as soon as possible. As a hexer he is quite ashamed that he does no
t know the best route, and that he has no sword on him at the moment. Help him find the shortest pat
h to Byteburg such that whenever he could meet some king of monster, previously he would havea chanc
e to get an appropriate sword to fight the beast. You need not worry about the number or weight of t
he swords - every hexer is as strong as an ox, so he can carry (virtually) unlimited number of equip
ment, swords in particular.
