Paper Route

As a cash-strapped student, you take a part-time job as a paper carrier. You are handed a paper route: a set of addresses conveniently labelled $1$ to $N$.

Every morning you start at the newspaper office, which is address number $0$. You must plan a route that delivers a newspaper to every address, and you also want to get to class right after you finish. There are exactly $N$ roads in your area connecting the addresses, and each takes a known time to traverse. You have also precomputed the time it takes to reach the campus from each location, including the newspaper office. How soon can you finish delivering and be in your seat at school?

The first line contains a single integer $N$ (the number of addresses, $1 \le N \le 100000$).

The next $N+1$ lines each contain an integer $c_i$ (for $i = 0, 1, \dots, N$, with $0 \le c_i \le 1{,}000{,}000{,}000$): the time it takes to get from location $i$ to campus.

The final $N$ lines each contain three integers $a$, $b$, $c$ ($0 \le a, b \le N$, $a \ne b$, $0 \le c \le 1{,}000$), describing a road between locations $a$ and $b$ that takes $c$ minutes to traverse.

You are guaranteed to be able to reach every address. (Recall that location $0$ is the newspaper office.)

Output the minimum time it takes to deliver all the papers and get to class.

It can be better to visit all the addresses, return to the office, and head to school from there.

For example, one route is $0 \to 1 \to 0 \to 2 \to 0 \to \text{school}$, taking $1 + 1 + 2 + 2 + 1 = 7$.