You work in the logistics service of a large transport company. Your task & mdash; Find the shortest time route between the two cities using the available road network.
rn
you have information about the time of the neighboring cities in the form Lines of the "AB: 120" format, where AB means the road between cities A and B, and 120 & mdash; Travel time in minutes. Bilateral roads.
rn
it is necessary to find the minimum travel time to the final city using the shortest search algorithm Ways.
Input format
the first line contains the number of roads n. gap
Output format
the minimum travel time or "route is impossible" if there is no way
Example
Input
5
AB: 60
BC: 90
AC: 120
CD: 45
bd: 30
a d
Hint
There will be no clue here, decide for yourself!