2019 USACO January


Every evening, Farmer John rings a giant bell that summons his cows to the barn for dinner. Eager to get to the barn as quickly as possible, they all follow the shortest possible route to get there. The farm is described by a set of n fields, conveniently numbered 1...n, with the barn residing in field 1. The fields are connected by a set of m bidirectional trails. Each trail has a travel time associated with it, and there is a path from every field to the barn using some set of trails.

Field i contains ci cows. Upon hearing the dinner bell, these cows all walk to the barn along a route that takes the minimum amount of time. If there are several routes tied for the minimum time, the cows take whichever of these is "lexicographically" smallest (i.e., they break ties between two routes by favoring the one using the lower-indexed field at the first place where the routes differ, so for example a path that visits fields 7, 3, 6, 1 would be preferable to one that visits 7, 5, 1, assuming both had the same travel time).

Farmer John is worried about the barn being far away from some fields. He adds up the travel time experienced by each cow, summed over all the cows, calling this number the total travel time. He would like to reduce this number as much as possible by adding one extra "shortcut" trail which has a travel time of t, from the barn (field 1) to some other field of his choosing. If a cow stumbles upon the shortcut trail while traveling along her usual path to the barn, she will take it if it gets her to the barn faster. Otherwise, a cow will follow her usual route, even if it might have been possible to use the shortcut to improve her travel time.

Please help Farmer John determine the greatest possible amount of decrease in total travel time he can achieve by adding his shortcut trail.


The first line contains n (1n10,000), m (n1m50000) and t (1t10000). The next line contains n integers c1...cn, each in the range 0...10000. The next m lines each describe a trail using three integers a, b and t, where the trail connects fields a and b and has travel time t. All travel times are in the range 1..25000.


Print the largest possible reduction in total travel time Farmer John can achieve.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 7
Output example #1
Source 2019 USACO January, Gold