Paper Route#2641
As a poor, tuition-ridden student, you have decided to take up a part-time job as a newspaper carrier. You have been hired and given your paper route: a set of addresses, conveniently labeled from to .
Every morning, you start at the newspaper office (which is labeled as address number in the route description). You need to plan a route to deliver a newspaper to every address, and you want to get to your place of study immediately after you finish. Fortunately, there are only roads between the serviced addresses in your area, and for each of them, the time required to traverse it is known.
In addition, you have data about how quickly you can get from some points to others, including the newspaper office, using, for example, a bicycle, skateboard, or hitchhiking. What is the minimum time to deliver all the newspapers and get to your place of study?
The first line contains the number of addresses (1 \leq n \leq 100000).
The next n + 1 lines each contain a single integer c_i (with numbering starting from i = 0, 0 \leq c_i \leq 1000000000)—the time required to get from location to the place of study.
Then follow lines, each containing three integers , , (0 \leq a, b \leq n, a \neq b, 0 \leq c \leq 1000). Each of these lines describes a road between two points, indicating the time in minutes required to traverse from to .
It is guaranteed that you can reach all addresses. (Recall that the newspaper office is at location .)
Print the minimum time required to deliver all the newspapers and reach your place of study.
Note: In this sample, it is better to visit each address, return to the office, and get to your place of study from there. For example, using the following route: 0 \to 1 \to 0 \to 2 \to 0 \to place of study = 1 + 1 + 2 + 2 + 1 = 7.
Example 1