Unfortunately for our ancestors and descendants, our current inability to enforce quarantine measures and failure to control the spread of disease has allowed the coronavirus to traverse a spontaneously constructed time portal, arriving at the same location in another arbitrary point in time. Thankfully, the countries here were able to respond rather quickly, acknowledging the threat as soon as it came through the portal. Governments are already planning to close international borders, but are unsure of how much time they have to do so.
Given access to a database consisting of all transportation connections among the countries, you are to determine how many days remain for a specific country to close all their borders, before the chronovirus arrives for its "community cleansing."
The first line will be an integer , the number of countries on Earth at this point in time.
The next lines of input will consist of each country's name (no whitespace), from 1 to .
The next line will be an integer , the number of international transport connections.
The next lines will consist of three integers each, separated by a space. The first two integers, and , mark the two countries linked by this transport connection . The final integer, , marks the number of days needed for transport along this route. Although transportation technology greatly varies throughout the technological eras, each country will always hold incoming cargo or passengers for 1 full day before allowing them to continue along their route.
The final line will be two integers and , marking the country from which chronovirus appeared and the country whose government would like to seal borders in time, respectively.
Print the minimum number of days it will take the chronovirus to reach the destination country , in the format of the sample outputs.
Sample Input 1
6 France Poland Russia Ottoman Persia China 7 1 2 4 1 4 7 2 3 4 2 4 1 3 5 3 4 5 8 5 6 9 1 5
Sample Output 1
The chronovirus will arrive in Persia in 13 days.
Sample Input 2
4 Fruitia Noodleland Cheeseburg Bacondorf 3 1 2 3 2 3 5 1 3 2 2 4
Sample Output 2
Bacondorf is completely safe!