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

Поле i содержит ci коров. Услышав обеденный звон, все эти коровы идут к коровнику по маршруту, который занимает минимум времени. Если имеется несколько маршрутов с минимальным временем, то коровы выбирают "лексикографически" наименьший из них (то есть они отдают предпочтение тому маршруту, который использует поле с более низким индексом в первом месте. Например, путь, который посещает поля 7, 3, 6, 1, будет предпочтительнее пути, который посещает 7, 5, 1, при условии, что у обоих было одинаковое время в пути).

Фермер Джон обеспокоен тем, что сарай находится далеко от полей. Он складывает время путешествия каждой коровы по всем коровам, называя это число общим временем в пути. Он хотел бы уменьшить это число насколько это возможно, добавив одну дополнительную "сокращенную" тропу, которая имеет время прохождения t, от сарая (поле 1) до некоторого другого поля по своему выбору. Если корова наткнется на короткую тропу во время своего обычного пути к сараю, она пойдет по ней, если она приведет ее к сараю быстрее. В противном случае корова будет следовать своим обычным маршрутом, даже если можно было бы использовать сокращенную тропу, чтобы сократить время в пути.

Помогите фермеру Джону определить максимально возможное сокращение общего времени в пути, которого он может достичь, добавив одну сокращенную тропу.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 10,000), m (n − 1 ≤ m ≤ 50000) и t (1 ≤ t ≤ 10000). Следующая строка содержит n целых чисел c1 ... cn, каждое из которых находится в диапазоне 0 ... 10000. Каждая из следующих m строк описывает тропу тремя целыми числами a, b и t (тропа соединяет поля a и b с временем в пути t). Время в пути находится в диапазоне от 1 до 25000.

Выходные данные

Выведите максимально возможное сокращение общего времени в пути которое может достичь фермер Джон.