Woburn Challenge 2017-18 Round 1 - Senior Division

There are ~N~ ~(2 \le N \le 1\,000)~ cities, with ~M~ ~(0 \le M \le 10\,000)~ roads running amongst them. The ~i^{th}~ road connects two different cities ~A_i~ and ~B_i~ ~(1 \le A_i, B_i \le N)~, and can be driven along in either direction in ~C_i~ ~(1 \le C_i \le 100)~ minutes. There may be multiple roads running directly between any given pair of cities.

You're taking a roadtrip across Canada from city ~1~ to city ~N~. You'd like to reach your destination in as little time as possible, by following a sequence of roads from city to city. However, as every Canadian knows, Tim Horton's pit stops are an essential part of any trip. It's vital that you stop at a Tim Horton's every ~L~ ~(1 \le L \le 100)~ minutes or less. In particular, you must never spend strictly more than ~L~ consecutive minutes during your trip outside of Tim Hortons' establishments, not counting any time before you leave city ~1~ or after you arrive at city ~N~.

Somehow, not every city has a Tim Horton's! If ~R_i = 0~, then the ~i^{th}~ city doesn't have one, and if ~R_i = 1~, then it does ~(0 \le R_i \le 1)~. Whenever you arrive in a city which has a Tim Horton's, you may choose to stop at it before continuing on your trip, which takes ~T~ ~(1 \le T \le 100)~ minutes.

What's the minimum amount of time required to reach city ~N~ from city ~1~ without ever spending more than ~L~ consecutive minutes outside of Tim Horton's establishments? If it can't be done, output -1 instead.

Subtasks

In test cases worth ~7/28~ of the points, ~L = 1~ and ~C_i = 1~ (for ~i = 1 \dots M~).
In test cases worth another ~10/28~ of the points, ~C_i = 1~ (for ~i = 1 \dots M~).

Input Specification

The first line of input consists of four space-separated integers, ~N~, ~M~, ~L~, and ~T~.
The next line consists of integers, ~R_{1 \dots N}~.
~M~ lines follow, the ~i^{th}~ of which consists of three space-separated integers, ~A_i~, ~B_i~, and ~C_i~, for ~i = 1 \dots M~.

Output Specification

Output a single integer, the minimum amount of time required to validly reach city ~N~ from city ~1~, or -1 if it's impossible.

Sample Input 1

6 10 6 3
0 1 0 1 0 0
1 3 3
1 4 6
1 4 7
2 4 2
2 5 4
2 6 3
3 4 6
4 5 1
4 6 6
5 6 5

Sample Output 1

14

Sample Input 2

2 1 10 1
1 1
2 1 11

Sample Output 2

-1

Sample Explanation 2

In the first case, one optimal route is as follows:

~1 \to 4~ (~6~ mins) Stop at Tim Horton's (~3~ mins) ~4 \to 2~ (~2~ mins) ~2 \to 6~ (~3~ mins)

In the second case, the single road between the cities is just too long for the trip to be possible, as driving along it would result in a lack of Tim Horton's for more than ~10~ minutes.