PROGRAMMING:It's Chinese New Year. Go home
Little CC's home is more than 1000 kilometers away from the school, and it takes dozens of hours by train. During the Spring Festival every year, little CC always racked their brains to find the most suitable transfer route.
The transfer problem of small CC is abstracted as follows:
There are $$n $$cities on the map, and $$M $$traffic routes connect the cities. The small CC needs to go through several transportation routes from the city to the city. Each traffic route will consume a certain amount of time, and the transfer time in transit cities will also consume a certain amount of time, and the transfer time at the starting point and the ending point is not included. Now, please write a program to help CC plan the way home, which must be the shortest path. If there are multiple paths with the same time, choose the one with the least transfer.
For example, little CC is going to return to Datong from Xiamen. The figure below shows the route map of little CC when she goes home. The square in the figure represents the transfer time, and the number on the line represents the travel time of the line.
(this map is only for illustration, and does not represent the real travel time and actual geographical location)
![ Train route map. PNG] (~ / 09a13237-60d4-42fb-940a-c4c24f728b43. Png#width half)
It can be seen from the figure that there are multiple paths to choose from, but there are only two paths with the shortest time (375 time)
1. Xiamen, Beijing and Datong, the journey time is 227 + 70 and the transfer time is 78;
2. Xiamen, Nanchang, Zhengzhou, Datong, travel time 65 + 64 + 125, transfer time 40 + 81.
At this time, small CC will choose the first line with less transfer times.
###Input format:
The first line is a positive integer $$n / leq500 $$, which indicates the number of cities.
Then there are $$n $$rows, each row followed by the city name and transfer time. The city name is no more than 40 characters, which is composed of upper and lower case letters. The transfer time is a positive integer no more than $$10 ^ 4 $.
Next is a positive integer, $$m / leq3n $$, indicating the number of traffic routes.
Next, the $$M $$line has three elements in each line, followed by two city names and the route time (a positive integer not greater than $$10 ^ 4 $).
The last line gives the city names of the starting point $$s $$and the destination $$t $$in turn.
###Output format:
**If there is a shortest route from the start to the end * *:
The output time of the first line is time-consuming (the transit time of the starting point and the ending point is not included).
The second line outputs the cities along the way (including the starting point and the ending point) in the order from the starting point to the ending point, and links with.
If there are multiple routes with the shortest time, the one with the least number of transfers will be output.
**If there is no route from the beginning to the end * *:
Output a line: "why not go home by plane“
###Input sample 1:
Examples in the diagram.
```in
ten
Datong 52
Xuzhou 87
Hefei 71
Nanchang 40
Zhengzhou 81
Shijiazhuang 56
Taiyuan 45
Nanjing 43
Beijing 78
Xiamen 55
twenty-two
Xiamen Beijing 227
Beijing Nanjing 170
Xiamen Hefei 95
Zhengzhou Shijiazhuang 41
Beijing Datong 70
Beijing Taiyuan 34
Taiyuan Datong 65
Taiyuan Shijiazhuang 19
Nanjing Hefei 10
Xuzhou Nanchang 102
Beijing Shijiazhuang 25
Xuzhou Beijing 157
Zhengzhou Xuzhou 37
Xiamen Xuzhou 139
Beijing Nanchang 201
Nanchang Xiamen 65
Zhengzhou Nanchang 64
Datong Zhengzhou 125
Hefei Xuzhou 46
Shijiazhuang Nanjing 198
Taiyuan Zhengzhou 43
Hefei Beijing 165
Xiamen Datong
```
###Output sample 1:
```out
three hundred and seventy-five
Xiamen->Beijing->Datong
```
###Input sample 2:
Unconnected graph. There are only two sides, Urumqi (Xinjiang) - Alashankou (Xinjiang), Ulanqab (formerly Jining, Inner Mongolia) - Hohhot (Inner Mongolia). There is no Alashankou Ulanqab path.
```in
four
Alashankou 50
Urumchi 65
Hohhot 69
Ulanqab 75
two
Urumchi Alashankou 96
Hohhot Ulanqab 125
Alashankou Ulanqab
```
###Output sample 2:
```out
Why not go home by plane?
```
answer：If there is no answer, please comment
The transfer problem of small CC is abstracted as follows:
There are $$n $$cities on the map, and $$M $$traffic routes connect the cities. The small CC needs to go through several transportation routes from the city to the city. Each traffic route will consume a certain amount of time, and the transfer time in transit cities will also consume a certain amount of time, and the transfer time at the starting point and the ending point is not included. Now, please write a program to help CC plan the way home, which must be the shortest path. If there are multiple paths with the same time, choose the one with the least transfer.
For example, little CC is going to return to Datong from Xiamen. The figure below shows the route map of little CC when she goes home. The square in the figure represents the transfer time, and the number on the line represents the travel time of the line.
(this map is only for illustration, and does not represent the real travel time and actual geographical location)
![ Train route map. PNG] (~ / 09a13237-60d4-42fb-940a-c4c24f728b43. Png#width half)
It can be seen from the figure that there are multiple paths to choose from, but there are only two paths with the shortest time (375 time)
1. Xiamen, Beijing and Datong, the journey time is 227 + 70 and the transfer time is 78;
2. Xiamen, Nanchang, Zhengzhou, Datong, travel time 65 + 64 + 125, transfer time 40 + 81.
At this time, small CC will choose the first line with less transfer times.
###Input format:
The first line is a positive integer $$n / leq500 $$, which indicates the number of cities.
Then there are $$n $$rows, each row followed by the city name and transfer time. The city name is no more than 40 characters, which is composed of upper and lower case letters. The transfer time is a positive integer no more than $$10 ^ 4 $.
Next is a positive integer, $$m / leq3n $$, indicating the number of traffic routes.
Next, the $$M $$line has three elements in each line, followed by two city names and the route time (a positive integer not greater than $$10 ^ 4 $).
The last line gives the city names of the starting point $$s $$and the destination $$t $$in turn.
###Output format:
**If there is a shortest route from the start to the end * *:
The output time of the first line is time-consuming (the transit time of the starting point and the ending point is not included).
The second line outputs the cities along the way (including the starting point and the ending point) in the order from the starting point to the ending point, and links with.
If there are multiple routes with the shortest time, the one with the least number of transfers will be output.
**If there is no route from the beginning to the end * *:
Output a line: "why not go home by plane“
###Input sample 1:
Examples in the diagram.
```in
ten
Datong 52
Xuzhou 87
Hefei 71
Nanchang 40
Zhengzhou 81
Shijiazhuang 56
Taiyuan 45
Nanjing 43
Beijing 78
Xiamen 55
twenty-two
Xiamen Beijing 227
Beijing Nanjing 170
Xiamen Hefei 95
Zhengzhou Shijiazhuang 41
Beijing Datong 70
Beijing Taiyuan 34
Taiyuan Datong 65
Taiyuan Shijiazhuang 19
Nanjing Hefei 10
Xuzhou Nanchang 102
Beijing Shijiazhuang 25
Xuzhou Beijing 157
Zhengzhou Xuzhou 37
Xiamen Xuzhou 139
Beijing Nanchang 201
Nanchang Xiamen 65
Zhengzhou Nanchang 64
Datong Zhengzhou 125
Hefei Xuzhou 46
Shijiazhuang Nanjing 198
Taiyuan Zhengzhou 43
Hefei Beijing 165
Xiamen Datong
```
###Output sample 1:
```out
three hundred and seventy-five
Xiamen->Beijing->Datong
```
###Input sample 2:
Unconnected graph. There are only two sides, Urumqi (Xinjiang) - Alashankou (Xinjiang), Ulanqab (formerly Jining, Inner Mongolia) - Hohhot (Inner Mongolia). There is no Alashankou Ulanqab path.
```in
four
Alashankou 50
Urumchi 65
Hohhot 69
Ulanqab 75
two
Urumchi Alashankou 96
Hohhot Ulanqab 125
Alashankou Ulanqab
```
###Output sample 2:
```out
Why not go home by plane?
```
answer：If there is no answer, please comment