The Need for Seed is a racing video game set in the fictional Fortune City. You, as a player of the game, need to carry seeds to the farmers by driving your car from one town to another. There are towns in Fortune City conveniently numbered from to . The towns are connected by weighted bidirectional roads. Each town has a unique positive integer difficulty level, . The time taken to go from one town to another can be different. When you drive from town to town , you will face obstacles if . The weight of each road denotes the time taken to go from one town to another.
There will be multiple races in the game. In each race, you will start from town and your goal is to reach town . Assume that whenever your car hits an obstacle, you lose all the seeds. So your goal is to reach town without facing any obstacles. You also want to minimize the time taken to go from town to town .
You need to determine the minimum time required to go from town to town .
Input will start with an integer , denoting the number of test cases.
Each test case will start with 3 space-separated integers , , and , where denotes the number of towns in Fortune City, denotes the number of roads connecting them, and denotes the number of races to be held.
The following line will contain space-separated integers where denotes the difficulty of the town.
The next lines each will contain 3 space-separated integers , , and indicating that there’s a bidirectional road between the town and town with that takes time.
The following lines each will contain two space-separated integers and , where denotes the starting town and denotes the goal town for the race.
where
where
Subtask #1 (40 points):
Subtask #2 (60 points): Original constraints
For each race, if there exists no path from town to town , print . Otherwise, print the time taken to reach . Print a newline after the output of each race.
Input | Output |
---|---|
1 3 3 2 3 2 1 0 1 1 0 2 3 1 2 1 0 2 2 0 | 2 -1 |