\problem{Of the Children}

\begin{quotation}
{\it This problem was withdrawn from the contest by a minute-1
clarification message sent to all teams.}

{\it The reason for the withdrawal was that, as of 24 hours before the
contest, the authoring team had only a single sample solution, and we
strongly prefer to move forward with a problem only after independent
confirmation by two or more authors.}
\end{quotation}

A nation-wide charity, {\em Won't Someone Think of the Children}, is
sending one of its celebrity spokespeople out on a coast-to-coast
publicity tour. Like many charities, they are bit strapped for funding
and need to plan carefully to make sure they can pay the celebrity's
travel expenses to get from their office on the west coast to the
final press event on the east coast.

Local offices of the charity have been taking pledges and collecting
donations to pay for this celebrity to visit their cities as part of
the tour. The national office has made no promises that the celebrity
will visit any of these intermediate locations, but hopes that these
locally collected funds can actually help fund the coast-to-coast
trip. In fact, without the help of the local offices, they aren't sure
they can afford to get their spokesperson to the final destination.

The trip will be paid for on an incremental basis. The celebrity can
only travel from one city to another if he or she has enough money to
pay for the transportation to that next city. Upon arrival at the
city, he or she can collect any money held there and use it to help
pay for the later legs of the journey. The celebrity can only visit a
given city once, lest multiple visits be considered an abuse of
their hospitality.

Given a list of cities that have invited the celebrity, the amount of
money raised by each city, and the travel costs between various pairs
of cities, what is the smallest amount of money that the home office
needs to provide the celebrity at the beginning of the journey to make
sure that he or she can make it all the way to the end without being
unable to pay for any leg of the trip?

\subsection*{Input}

Input will consist of one or more datasets. Each dataset begins with a
line containing a single integer, $N$, $2 \leq N < 24$, indicating the
number of cities involved. A value of zero for $N$ signals the end of
input.

Cities are identified by integers in the range $0\ldots N-1$, with
city $0$ being the home office and starting point of the journey, and
city $N-1$ being the final destination city for the journey.

The first line of the dataset is followed by $N-2$ lines, each
containing an integer in the range $0\ldots \num{10000}$ indicating the
amount of money collected by the cities numbered $1 \ldots N-2$. (The
amount of money at city $N-1$ is irrelevant and the amount of money to
be provided at city $0$ is what you need to compute).

This is followed by at least $1$ and up to $N(N-1)/2$ lines, each
containing three integers $i$, $j$, \& $c$.  $i$ and $j$ are distinct
integers in the range $0\ldots N-1$ identifying two cities and $c$ is
the cost to travel from one of those cities to the other, $0 < c <
\num{10000}$. The cost is the same when traveling from $i$ to $j$ as it is
when traveling from $j$ to $i$.  The end of this list of potential travel
expenses is indicated by a line containing negative values for $i$,
$j$, and $c$.


\subsection*{Output}

For each dataset print a single line of output. 

If it is possible to reach city $N-1$ from city $0$, print the
smallest amount of money that the celebrity needs to be given at city
$0$ in order to guarantee reaching city $N-1$.

If it is not possible to reach city $N-1$ when starting from city $0$, print $-1$.



\subsection*{Example}

Given the input:

\verbfile{OfTheChildren/test0.in}


the output should be:

\verbfile{OfTheChildren/test0.expected}



