Найкоротший шлях
Кожного вечора фермер Джон дзвонить у великий дзвін, щоб покликати своїх корів до хліва на вечерю. Прагнучи дістатися до хліва якомога швидше, всі корови обирають найкоротший шлях. Ферма складається з n полів, пронумерованих від 1 до n, причому хлів розташований на полі 1. Поля з'єднані набором з m двонаправлених стежок. Кожна стежка має певний час проходження, і з будь-якого поля завжди можна дістатися до хліва, використовуючи певний набір стежок.
Поле i містить c[i] корів. Почувши дзвін, всі ці корови прямують до хліва по маршруту, який займає найменше часу. Якщо існує кілька маршрутів з однаковим мінімальним часом, корови обирають "лексикографічно" найменший з них (тобто вони віддають перевагу маршруту, який використовує поле з меншим індексом на першому відмінному місці. Наприклад, шлях, що проходить через поля 7, 3, 6, 1, буде кращим за шлях через 7, 5, 1, якщо обидва мають однаковий час у дорозі).
Фермер Джон стурбований тим, що хлів може бути занадто далеко від полів. Він підраховує час подорожі кожної корови і називає це загальним часом у дорозі. Він хоче зменшити цей час, додавши одну додаткову "скорочену" стежку з часом проходження t, яка веде від хліва (поле 1) до будь-якого іншого поля на вибір. Якщо корова натрапить на скорочену стежку під час свого звичайного маршруту до хліва, вона скористається нею, якщо це скоротить час у дорозі. В іншому випадку корова буде слідувати своїм звичайним маршрутом, навіть якщо скорочена стежка могла б зменшити час у дорозі.
Допоможіть фермеру Джону визначити максимально можливе скорочення загального часу у дорозі, яке він може досягти, додавши одну скорочену стежку.
Вхідні дані
Перший рядок містить n (1 ≤ n ≤ 10,000), m (n − 1 ≤ m ≤ 50000) і t (1 ≤ t ≤ 10000). Другий рядок містить n цілих чисел c[1] ... c[n], кожне з яких знаходиться в діапазоні 0 ... 10000. Кожен з наступних m рядків описує стежку трьома цілими числами a, b і t (стежка з'єднує поля a і b з часом у дорозі t). Час у дорозі знаходиться в діапазоні від 1 до 25000.
Вихідні дані
Виведіть максимально можливе скорочення загального часу у дорозі, яке може досягти фермер Джон.