As a presidential candidate, you need to cover the most territory in the least amount of time, blazing through miles of backwoods America on your way from one big city to another in an effort drum up enough support to win the election and make the massive amounts of money you showered on your campaign ads! Your staff is competent enough to find out what cities are connected to what others and how much time you are likely to have to spend traveling both within and between the cities, but they aren't quite competent enough to figure out what the best way for you to go would be.
However, since you've been well educated in the ways of data structures and algorithms, you are wise about these sorts of things. You know programming. To circumvent your staff, you decide to take matters into your own hands and write a program to find the shortest routes between two cities between which you need to travel, including time spent in all the cities on the route. Beware, it may not always be possible to travel from city 1 to city n.
Good luck with the campaign!
The first line of input will be n, the number of cities.
The second line will be n integers showing the delay for
city 
. During the trip, delays apply to cities
1 and n as well as all intermediate cities.
The remaining lines with be a list of
ordered triples (x,y,d) indicating a path from city x to
city y with delay d. You may also travel from city y to
city x with the same delay. All delays are integers.
The end of the list will be a triple where x = 0.
Your goal is to find the quickest time to get from city 1 to city n. You do not have to visit all cities. You may assume all delays within a city or between cities will be less than or equal to 100, and the maximum number of cities is 100.
The output consists of two lines. If no path exists from city 1 to city n, output ``No path found". Otherwise, on the first line output ``Shortest time: " and the shortest time from city 1 to city n. On the second line output ``Shortest path: ", followed by the list of cities on the shortest path in the order visitied, starting from city 1 and ending at city n. If there are multiple shortest paths, you may output any such path.
Input:
3 10 20 30 1 2 1 2 3 3 3 1 2 0 0 0
Output:
Shortest time: 42 Shortest path: 1 3
Input:
6 2 12 15 5 8 3 1 2 23 1 3 91 3 2 12 6 4 21 6 5 12 4 5 13 0 0 0
Output:
No path found
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |
| Input 5 | Output 5 |
| Input 6 | Output 6 |
| Input 7 | Output 7 |
| Input 8 | Output 8 |