Woburn Challenge 2017-18 Round 1 - Senior Division

There are $N$ $(2\le N\le 1000)$ cities, with $M$ $(0\le M\le 10000)$ 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.