Treasure Hunt

You are given a treasure map with n checkpoints and m bidirectional paths connecting them. Each checkpoint i contains a certain number of treasure chests, represented by an array. Starting at checkpoint 0, you have a limited time t to collect treasures. You can travel along any path, where each path between checkpoints u and v takes w time units. A checkpoint is considered reachable if the shortest travel time from checkpoint 0 is at most t seconds.

Your task is to compute the maximum number of treasure chests you can collect by summing the treasures at all checkpoints that are reachable within the given time. The shortest distance from checkpoint 0 to any other checkpoint can be computed using Dijkstra's algorithm. In mathematical terms, let \(d(i)\) be the shortest distance from checkpoint 0 to checkpoint \(i\). Then, the answer is given by:

[ \text{Answer} = \sum_{i=0}^{n-1} \mathbf{1}_{{d(i) \leq t}} \times \text{treasure}[i] ]

It is guaranteed that the map is connected by the given paths (if a path exists) and that each path is bidirectional.

inputFormat

The input is given via stdin and has the following format:

n m t
c0 c1 c2 ... c(n-1)
u1 v1 w1
u2 v2 w2
...
um v m w m

Here:

• n is the number of checkpoints.
• m is the number of paths.
• t is the time limit.
• The next line contains n integers where the i-th integer represents the number of treasure chests at checkpoint i.
• The following m lines each contain three integers u, v, and w indicating that there is a bidirectional path between checkpoints u and v with travel time w.

outputFormat

Output via stdout a single integer: the maximum number of treasure chests that can be collected by visiting all checkpoints reachable (i.e., those for which the shortest distance from checkpoint 0 is at most t).

## sample

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

21