Прыжки между вселенными
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Для перемещения Мигель О'Хара использует свои высокотехнологичные портальные часы. Но самые первые версии этих часов были не настолько развиты, и не позволяли сразу путешествовать в произвольные вселенные. А именно, у часов был параметр энергетического уровня, который изначально был равен $$$0$$$.

Каждый портал характеризуется некоторой характеристикой $$$w$$$ — минимальным значением энергетического уровня, необходимым для использования этого портала. Если значение энергетического уровня часов меньше $$$w$$$, то воспользоваться этим порталом сейчас нельзя. К счастью, есть способ увеличить энергетический уровень: при первом попадании во вселенную $$$i$$$ энергетический уровень часов навсегда увеличивается на $$$a_i$$$.

Мигель задумался, какое максимальное значение энергетического уровня он может получить на старом прототипе часов, если посетит все вселенные, в которые сможет попасть, начав свой путь из вселенной номер $$$s$$$? Помогите ему ответить на этот вопрос.

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

В первой строке входных данных даны три целых числа $$$n$$$, $$$m$$$ и $$$s$$$ — количество вселенных, количество порталов между этими вселенными, и номер вселенной, из которой Мигель начинает свои перемещения ($$$1 \le s \le n \le 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$).

Во второй строке входных данных через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — значения, на которые увеличивается энергетический уровень часов при первом посещении каждой вселенной ($$$1 \le a_i \le 10^9$$$).

В следующих $$$m$$$ строках дано описание порталов. Описание портала под номером $$$i$$$ содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$, и определяет портал между вселенными $$$u_i$$$ и $$$v_i$$$, для использования которого нужно иметь силу часов не меньше $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$0 \le w_i \le 10^9$$$).

Граф связей между вселенными не содержит кратных ребер и петель, однако не обязательно связен.

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

В единственной стоке выведите одно целое число — максимальное значения энергетического уровня часов, которое может получить Мигель.

Примеры

Входные данные
5 4 1
1 1 1 1 1
1 2 2
1 3 1
1 4 3
1 5 5
Выходные данные
4
Входные данные
4 3 1
3 2 1 10
1 2 3
2 3 5
1 3 4
Выходные данные
6