Shortcut
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 c[i] 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.
Input
The first line contains n (1 ≤ n ≤ 10,000), m (n − 1 ≤ m ≤ 50000) and t (1 ≤ t ≤ 10000). The next line contains n integers c[1]...c[n], 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.
Output
Print the largest possible reduction in total travel time Farmer John can achieve.