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 |

Tue Mar 24 16:22:12 EST 1998