Лич Сандро решил пойти в подземелье за легендарными сокровищами. Подземелье является запутанным переплетением коридоров и комнат. Каждый коридор имеет ровно один вход и ровно один выход, и передвигаться по нему можно только в направлении от входа к выходу

D. Подземелья и личи ограничение по времени на тест: 4.5 секунд ограничение по памяти на тест: 512 мегабайт
Лич Сандро решил пойти в подземелье за легендарными сокровищами. Подземелье является запутанным переплетением коридоров и комнат. Каждый коридор имеет ровно один вход и ровно один выход, и передвигаться по нему можно только в направлении от входа к выходу (но не в обратном). Чтобы получить легендарные сокровища, Сандро нужно преодолеть\( K \)любых коридоров, не обязательно различных. Каждый коридор характеризуется уровнем магической ауры, и, чтобы пройти по нему, Сандро должен иметь при себе артефакт такого же или выше уровня. Изначально Сандро может телепортироваться в любую комнату и начать свой поход из неё. Помогите личу Сандро понять, артефакт какого минимального уровня ему понадобится, чтобы получить легендарные сокровища.
Входные данные: Первая строка содержит целые числа\( N, M \) и \( K \) - количество комнат в подземелье, количество коридоров в подземелье и сколько коридоров нужно преодолеть личу Сандро, чтобы получить легендарные сокровища ( \( 1 \leq N, M \leq 10^{5} ; 0 \leq K \leq 10^{12} \) ).

Каждая из следующих \( M \) строк является описанием коридора и содержит целые числа \( u_{i}, v_{i}, s_{i} \) - комната, в которой находится вход в \( i \)-й коридор, комната, в которой находится выход из \( i \)-го коридора, и уровень магической ауры \( i \)-го коридора
\[
\left(1 \leq u_{i}, v_{i} \leq N ; 0 \leq s_{i} \leq 10^{12}\right)
\]Выходные данные:
Если Лич Сандро может получить легендарные сокровища, выведите неотрицательное целое число - минимальный уровень артефакта, который ему для этого понадобится. Если сокровища никак не получить, выведите -1 .\( \)\( \)