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

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

Каждая из следующих M строк является описанием коридора и содержит целые числа u{i}, v{i}, s_i - комната, в которой находится вход в i-й коридор, комната, в которой находится выход из i-го коридора, и уровень магической ауры i-го коридора
≤ft(1 ≤ u{i}, v{i} ≤ N ; 0 ≤ s_i ≤ 10¹²\right)Выходные данные:
Если Лич Сандро может получить легендарные сокровища, выведите неотрицательное целое число - минимальный уровень артефакта, который ему для этого понадобится. Если сокровища никак не получить, выведите -1 .