Woburn Challenge 2015-16 Round 1 - Senior Division

It's no surprise that the Programming Enrichment Group at Woburn participates in a wide number of programming contests. However, not all contests are held at the same place (worry not – the Woburn Challenge finals will be held at a single location). In fact if too many people register for a contest, the contest organizers may even demand that the same contest be held in two entirely different towns! This will make it a lot harder for our young Woburnites to compete in the contest, but certainly won't stop them from trying.

There are ~N~ ~(2 \le N \le 10^5)~ towns uniquely numbered with integers from ~1~ to ~N~, and ~M~ ~(1 \le M \le 10^5)~ one-way roads running amongst them. Specifically, the ~i~-th road (for ~i = 1 \dots M~) allows one to travel from a town ~A_i~ to a different town ~B_i~ ~(1 \le A_i, B_i \le N; A \ne B)~ and has a distance of ~D_i~ ~(1 \le D_i \le 100)~ kilometres. No two roads run between the same pair of towns in the same direction. A very large programming contest is soon to be held across two locations, with the main contest site located in town ~1~ and the secondary contest site located in town ~2~. A non-zero number of Woburnites will be competing in this contest, with ~C_i~ ~(0 \le C_i \le 10^6)~ of them living in town ~i~ (for each ~i = 1 \dots N~). Each competitor must select one of the two contest sites and travel to it using a sequence of roads. This sequence is possibly empty, if they're fortunate enough to live in the same town as their chosen contest site.

There is a catch! Resources are limited at the second contest site, so the contest organizers have insisted that no more than ~K~ ~(0 \le K \le 10^9)~ of the competitors attend the secondary site (located in town ~2~). Given that the Woburnites collaborate to come up with the best travel strategy, you must help them determine the minimum total combined distance that they must travel in order to all attend the contest, such that no more than ~K~ of them travel to the secondary site.

In test cases worth 60% of the marks, ~N \le 100~.
In a subset of those cases worth 30% of the marks, ~C_i \le 1~ (for ~i = 1 \dots N~).

Input Specification

Line ~1~ of input will contain three space-separated integers, the values of ~N~, ~M~, and ~K~, respectively representing the number of towns, roads, and the maximum number of Woburnites that may attend the second site.
There will be ~N~ lines to follow. The ~i~-th of these lines (for ~i = 1 \dots N~) will contain a single integer ~C_i~, representing the number of Woburnites living in town ~i~.
There will be ~M~ lines to follow. The ~i~-th of these lines (for ~i = 1 \dots M~) will contain three space-separated integers, the values of ~A_i~, ~B_i~, and ~D_i~ representing the ~i~-th one-way road.

Output Specification

The output should consist of a single integer. If it is possible for the Woburnites to travel to all contest sites with no more than ~K~ of them attending the secondary site, then output the minimum total combined distance that they must travel to do so. Output -1 if it is impossible for all of them to reach a contest site while satisfying the condition. Please note that the answer may not necessarily fit in a 32-bit integer.

Sample Input

4 5 5
2
1
5
7
1 2 1
3 2 1
3 4 1
4 1 1
4 3 1

Sample Output

13

Explanation

There are ~4~ towns and ~5~ roads between them. At most ~5~ people may attend the second contest site. Each road happens to have a distance of ~1~. An optimal travel strategy is as follows.

• We let competitors from towns ~1~ and ~2~ attend the contest sites at their respective towns (incurring an additional ~0~ kilometres to our total distance).
• We let all ~7~ of our competitors from town ~4~ travel to the main contest site (incurring a total of ~7~ kilometres).
• We let ~4/5~ of the competitors from town ~3~ travel to the secondary contest site (incurring a total of ~4~ kilometres).
• We let the remaining competitor from town ~3~ must travel to the main site through town ~4~ (incurring an additional ~2~ kilometres to our total distance).

The total distance traveled across all of the competitors is ~0+7+4+2 = 13~ kilometres.