Of the Children

This problem was withdrawn from the contest by a minute-1 clarification message sent to all teams.

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.

A nation-wide charity, Won't Someone Think of the Children, is sending one of its celebrity spokespeople on a coast-to-coast publicity tour. Like many charities, it is short on funds and must plan carefully to pay the celebrity's travel expenses from its 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 the 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 help fund the coast-to-coast trip. Without the help of the local offices, the national office is not sure it can afford to get the spokesperson to the final destination.

The trip is paid for incrementally. The celebrity can travel from one city to another only if he or she has enough money to pay for the transportation to that next city. Upon arrival at a city, the celebrity collects any money held there and uses it to pay for the later legs of the journey. The celebrity can visit a given city only once.

Given the cities that have invited the celebrity, the amount of money raised by each city, and the travel costs between pairs of cities, what is the smallest amount of money the home office must provide at the beginning of the journey so that the celebrity can reach the end without being unable to pay for any leg of the trip?

Input consists of one or more datasets. Each dataset begins with a line containing a single integer $N$, $2 \leq N < 24$, the number of cities. A value of 0 for $N$ marks the end of input.

Cities are numbered $0 \ldots N-1$. City 0 is the home office and the starting point. City $N-1$ is the final destination.

The next $N-2$ lines each contain an integer in the range $0 \ldots 10\,000$, the money collected by cities $1 \ldots N-2$. The money at city $N-1$ is irrelevant, and the amount to be provided at city 0 is what you compute.

The following lines each contain three integers $i$, $j$, and $c$, where $i$ and $j$ are distinct cities in the range $0 \ldots N-1$ and $c$ is the travel cost between them, with $0 < c < 10\,000$. The cost is the same in both directions. There is at least 1 and at most $N(N-1)/2$ such line. The list ends with a line where $i$, $j$, and $c$ are all negative.

For each dataset, print a single line.

If city $N-1$ can be reached from city 0, print the smallest amount of money the celebrity must be given at city 0 to guarantee reaching city $N-1$.

If city $N-1$ cannot be reached from city 0, print $-1$.