Your boss has hired you to drive a big truck, transporting
items between two locations in a city. You’re given a
description of the city, with locations of interest and the
lengths of roads between them. Your boss requires that you take
a shortest path between the starting and ending location, and
she’ll check your odometer when you’re done to make sure you
didn’t take any unnecessary side trips. However, your friends
know you have plenty of unused space in the truck, and they
have asked you to stop by several locations in town, to pick up
items for them. You’re happy to do this for them. You may not
be able to visit every location to pick up everything your
friends want, but you’d like to pick up as many items as
possible on your trip, as long as it doesn’t make the path any
longer than necessary.
The two graphs above show examples of what the city may look
like, with nodes representing locations, edges representing
roads and dots inside the nodes representing items your friends
have asked you to pick up. Driving through a location allows
you to pick up all the items there; it’s a big truck, with no
limit on the items it can carry. In the graph on the left, for
example, you have to drive the big truck from location
$1$ to location
$6$. If you follow the
path $1 \rightarrow 2 \rightarrow
3 \rightarrow 6$, the length is $9$, and you’ll get to pick up
$4$ items. Of course, it
would be better to drive $1
\rightarrow 4 \rightarrow 5 \rightarrow 6$; that’s still
a length of $9$, but going
this way instead lets you pick up an additional item. Driving
$1 \rightarrow 4 \rightarrow 3
\rightarrow 6$ would let you pick up even more items,
but it would make your trip longer, so you can’t go this
way.
Input
The first line of input contains an integer, $n$ ($2
\leq n \leq 100$), giving the number of locations in the
city. Locations are numbered from $1$ to $n$, with location $1$ being the starting location and
$n$ being the destination.
The next input line gives a sequence of $n$ integers, $t_1 \ldots t_ n$, where each
$t_ i$ indicates the
number of items your friends have asked you to pick up from
location $i$. All the
$t_ i$ values are between
$0$ and $100$, inclusive. The next input line
contains a nonnegative integer, $m$, giving the number of roads in the
city. Each of the following $m$ lines is a description of a road,
given as three integers, $a \: b
\: d$. This indicates that there is a road of length
$d$ between location
$a$ and location
$b$. The values of
$a$ and $b$ are in the range $1 \ldots n$, and the value of
$d$ is between
$1$ and $100$, inclusive. All roads can be
traversed in either direction, there is at most one road
between any two locations, and no road starts and ends at the
same location.
Output
If it’s not possible to travel from location $1$ to location $n$, just output out the word
“impossible”. Otherwise, output the length of a shortest path
from location $1$ to
location $n$, followed by
the maximum number of items you can pick up along the way.
Sample Input 1 
Sample Output 1 
6
1 1 2 3 1 0
7
1 2 2
2 3 3
3 6 4
1 4 4
4 3 2
4 5 3
5 6 2

9 5

Sample Input 2 
Sample Output 2 
9
1 1 1 1 1 1 1 1 1
10
1 2 3
2 5 3
1 6 2
6 7 2
7 5 2
5 3 1
3 4 2
4 9 3
5 8 2
8 9 4

12 7

Sample Input 3 
Sample Output 3 
2
5 5
0

impossible
