smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2020 P5 - Chronovirus

data_usage Points
timer Time Limit
linear_scale Memory Limit

Problem Statement

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."

Input Specification

The first line will be an integer N,1N2000N, 1 ≤ N ≤ 2000, the number of countries on Earth at this point in time.

The next NN lines of input will consist of each country's name (no whitespace), from 1 to NN.

The next line will be an integer M,1M100000M, 1 ≤ M ≤ 100000, the number of international transport connections.

The next MM lines will consist of three integers each, separated by a space. The first two integers, ii and j,1i,jNj, 1 ≤ i, j ≤ N, mark the two countries linked by this transport connection . The final integer, t,0t90t, 0 ≤ t ≤ 90, 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 aa and b,1a,bNb, 1 ≤ a, b ≤ N, marking the country from which chronovirus appeared and the country whose government would like to seal borders in time, respectively.

Output Specification

Print the minimum number of days it will take the chronovirus to reach the destination country bb, in the format of the sample outputs.

Sample Input 1

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

1 2 3
2 3 5
1 3 2
2 4

Sample Output 2

Bacondorf is completely safe!