Найкоротший шлях#10337

Найкоротший шлях

1 секунда

128 мегабайтів

Легка

Кожного вечора фермер Джон дзвонить у великий дзвін, щоб покликати своїх корів до хліва на вечерю. Прагнучи дістатися до хліва якомога швидше, всі корови обирають найкоротший шлях. Ферма складається з $n$ полів, пронумерованих від $1$ до $n$ , причому хлів розташований на полі $1$ . Поля з'єднані набором з $m$ двонаправлених стежок. Кожна стежка має певний час проходження, і з будь-якого поля завжди можна дістатися до хліва, використовуючи певний набір стежок.

Поле $i$ містить $c_{i}$ c_i корів. Почувши дзвін, всі ці корови прямують до хліва по маршруту, який займає найменше часу. Якщо існує кілька маршрутів з однаковим мінімальним часом, корови обирають "лексикографічно" найменший з них (тобто вони віддають перевагу маршруту, який використовує поле з меншим індексом на першому відмінному місці. Наприклад, шлях, що проходить через поля $7$ , $3$ , $6$ , $1$ , буде кращим за шлях через $7$ , $5$ , $1$ , якщо обидва мають однаковий час у дорозі).

Фермер Джон стурбований тим, що хлів може бути занадто далеко від полів. Він підраховує час подорожі кожної корови і називає це загальним часом у дорозі. Він хоче зменшити цей час, додавши одну додаткову "скорочену" стежку з часом проходження $t$ , яка веде від хліва (поле $1$ ) до будь-якого іншого поля на вибір. Якщо корова натрапить на скорочену стежку під час свого звичайного маршруту до хліва, вона скористається нею, якщо це скоротить час у дорозі. В іншому випадку корова буде слідувати своїм звичайним маршрутом, навіть якщо скорочена стежка могла б зменшити час у дорозі.

Допоможіть фермеру Джону визначити максимально можливе скорочення загального часу у дорозі, яке він може досягти, додавши одну скорочену стежку.

Вхідні дані

Перший рядок містить $n$ ( $1 \leq n \leq 10000$ 1 \le n \le 10000), $m$ ( $n - 1 \leq m \leq 50000$ n - 1 \le m \le 50000) і $t$ ( $1 \leq t \leq 10000$ 1 \le t \le 10000). Другий рядок містить $n$ цілих чисел $c_{1}, \dots, c_{n}$ c_1, \ldots, c_n, кожне з яких знаходиться в діапазоні $0 \dots 10000$ . Кожен з наступних $m$ рядків описує стежку трьома цілими числами $a$ , $b$ і $t$ (стежка з'єднує поля $a$ і $b$ з часом у дорозі $t$ ). Час у дорозі знаходиться в діапазоні від $1$ до $25000$ .

Вихідні дані

Виведіть максимально можливе скорочення загального часу у дорозі, яке може досягти фермер Джон.

Приклади

Приклад 1