Maximizing Total Time Savings by Adding a Shortcut

Farmer John rings a giant bell every evening to call his cows to the barn located at grassland 1. The cows, eager for dinner, always follow their unique shortest route to the barn. The farm consists of N grasslands (numbered 1 through N) and M bidirectional roads connecting them. Each road has an associated travel time, and it is guaranteed that every grassland can reach the barn.

Each grassland i has c_i cows. When the dinner bell sounds, all cows in grassland i follow the unique shortest path (if there are several shortest paths, they choose the one that is lexicographically smallest; that is, at the first branching the path passing through the smaller-numbered grassland is chosen) toward the barn.

Farmer John is concerned that some grasslands are very far from the barn. He computes the total moving time by summing the travel times of all cows along their routes. To reduce this total moving time, Farmer John considers adding an extra road, called a shortcut. This shortcut connects the barn (grassland 1) to some other grassland of his choice and has a travel time of T (with 1 ≤ T ≤ 10,000).

When a cow, on her usual path to the barn, passes through the grassland where the shortcut is available, she will take the shortcut if it allows her to reach the barn faster; otherwise, she continues on her normal route, even if the shortcut might offer a shorter overall travel time if taken independently.

For a chosen grassland X (other than 1) where the shortcut is placed, let d(X,1) be the travel time from X to the barn along the original path. Every cow whose route passes through X can reduce her travel time by d(X,1) - T if d(X,1) > T (otherwise, no benefit is gained). If P(X) is the total number of cows whose unique route to the barn includes grassland X, then the total time saved by placing the shortcut at X is (d(X,1) - T) × P(X) (only if d(X,1) > T; otherwise, the saving is 0).

Your task is to help Farmer John choose the optimal grassland to place the shortcut so that the total moving time is reduced as much as possible. Output the maximum achievable reduction.

Note: Roads are bidirectional. The unique path for each cow is determined by first finding any shortest path; if there is a tie, choose the lexicographically smallest path, meaning that at the first divergence, the path that goes through the grassland with the smaller number is chosen.

inputFormat

The first line contains three integers: N, M, and T — the number of grasslands, the number of roads, and the travel time of the shortcut, respectively.

The second line contains N integers: c1, c2, ..., cN, where c_i is the number of cows in grassland i.

The next M lines each contain three integers u, v, and w indicating that there is a bidirectional road between grasslands u and v with travel time w.

It is guaranteed that (1) 1 ≤ N ≤ 10,000, (2) N-1 ≤ M ≤ 50,000, and (3) there is at least one path from every grassland to the barn (grassland 1).

outputFormat

Output a single integer, the maximum total time reduction that can be achieved by adding the shortcut optimally.

sample

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

30