407932: GYM102944 I Isle Royale

Isle Royale is the only national park in Michigan. Since Isle Royale is a large island located very far north in Lake Superior, people rarely visit during the winter, and the wildlife and natural scenery are quite well preserved. The only access to the island is by a ferry that runs once a day. You have decided to write a video game about an adventure on Isle Royale. The map of the island is modeled as a graph with $$$N$$$ recreation sites (vertices) and $$$M$$$ paths connecting these sites (undirected edges).

In this game, a hero (the main character) begins at the entrance, recreation site $$$1$$$, where the ferry docks. Her objective is to travel along the paths to the campground at site $$$N$$$. Easy, right? But there are moose on the island! And a charging moose is three-quarters of a ton of dumb, terrifying fury. In fact, there is one moose at each recreation site $$$i$$$, where $$$1\le i\le N-1$$$.

Now there are two ways to deal with a moose (in the game – don't do this in real life): either stand perfectly still or climb a tree. The advantage of standing still is that it conserves energy, (but the moose does not leave). The advantage of climbing a tree is that the moose becomes frustrated and fades back into the forest, never to return, and the hero can advance. At each recreation site $$$i$$$, there is one tree and the hero must expend a certain amount of energy, $$$P_i$$$, to climb that tree. The hero begins the game with $$$E$$$ energy units, which you may assume is positive. Whenever the hero is at a recreation site $$$i\le N-1$$$, she may spend one minute executing one of the three following actions:

• Stand still. If her energy when she arrives at $$$i$$$ is less than $$$E$$$, she recovers one energy unit.
• Climb a tree. This costs her $$$P_i$$$ energy units.
• Move along a path to another recreation site $$$j$$$. This option is available only when the moose has left. Also, the hero loses $$$D_{i, j}$$$ energy units walking along the path.

Our hero may never have a negative amount of energy, even when she reaches the destination site $$$N$$$. As the game designer, you would like to ensure that the game is difficult but fun. Can you write a program that calculates the shortest possible amount of time (in minutes) a hero needs to travel to site $$$N$$$?

The first line contains three integers $$$N, M, E$$$ ($$$1\le N, M\le 10^4$$$, $$$1\le E\le 10^9$$$). In the second line there are $$$N-1$$$ integers $$$P_1, P_2, \ldots, P_{N-1}$$$ ($$$1\le P_i\le E$$$). In each of the next $$$M$$$ lines, there are three integers $$$u_i$$$, $$$v_i$$$, and $$$D_{u_i, v_i}$$$ ($$$1\le u_i, v_i\le N$$$, $$$0\le D_{u_i, v_i}\le E$$$). You may assume that there is always a way for a hero to avoid the moose and get to the destination site $$$N$$$.

Output the minimum amount of time it takes the hero to arrive at site $$$N$$$.

5 5 100
60 30 40 20
1 2 5
2 3 10
2 4 15
3 5 20
4 5 25

61

5 4 100
10 10 10 10
1 2 10
2 3 10
3 4 10
4 5 10

8

5 4 100
100 100 100 100
1 2 100
2 3 100
3 4 100
4 5 100

708