Каждый день фермер Джон звонит в гигантский колокол, созывая своих
коров в амбар на обед. Все коровы идут кратчайшим путём.
Ферма описывается как \(N\) полей (\(1 \leq N \leq 10,000\)),
последовательно пронумерованных \(1 \ldots N\), амбар находится в
поле 1. Поля соединены \(M\) двунаправленными тропинками
(\(N-1 \leq M \leq 50,000\)). С каждой тропинкой ассоциировано время
её прохождения, и от любого поля имеется путь к амбару, состоящий
из некоторого множества тропинок.
Поле \(i\) содержит \(c_i\) коров. Услышав колокол, все коровы двигаются
к амбару так, чтобы потратить минимальное количество времени.
Если имеется несколько путей с минимальным временем, коровы выбирают
"лексикографически минимальный" путь. Например, путь через поля 7,3,6,1
лексикографически минимальнее, чем путь 7,5,1.
ФД хочет сократить общее время движения (сумму времён движения всех
коров) как можно больше добавлением одной сокращающей тропинки,
которая имеет время прохождения \(T\) (\(1 \leq T \leq 10,000\)), от амбара
(поле 1) до другого поля, которое он выберет. Если корова встретится
с этой сокращающей тропинкой на своём обычном пути, тогда корова пойдёт
по этой тропинке, если в результате уменьшится время её прихода в амбар.
Иначе, корова пойдёт по своему обычному маршруту, даже если бы она могла
уменьшить своё время в пути, используя сокращающую тропинку.
Помогите ФД определить наибольшую величину уменьшения суммарного
времени движения, которое он может достичь добавлением сокращающей
тропинки.
ФОРМАТ ВВОДА (файл shortcut.in):
Первая строка ввода содержит \(N\), \(M\), \(T\). Каждая из \(N\) последующих
строк содержит \(c_1 \ldots c_N\) - целое число в интервале \(0 \ldots 10,000\).
Каждая из последующих \(M\) строк описывает тропинку тремя целыми числами
\(a\), \(b\), \(t\), обозначающими, что поля \(a\) и \(b\) соединены тропинкой
время прохождения которой равно \(t\). Все времена в интервале \(1 \ldots 25,000\).
ФОРМАТИ ВВОДА (файл shortcut.out):
Выведите наибольшее возможное сокращение суммарного времени движения,
которое может добиться ФД.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
40
|