ЗАДАЧА C

Йоулупукки

Имя входного файла:joulu.in
Имя выходного файла:joulu.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

Йоулупукки был приятно удивлен, когда вчера ему позвонил его старый друг, украинский коллега Миколай Бородатий© и пригласил поучаствовать в IV открытом чемпионате Харькова по спортивному программированию. Еще бы, не часто провинциальному финскому Деду Морозу выпадает шанс участвовать в соревновании столь высокого уровня.

Поэтому, еще за неделю до Чемпионата, Йоулупукки вместе со своей женой Муори вышел в интернет и стал разрабатывать маршрут поездки. Дело это непростое, ведь путь из Финляндии в Украину неблизкий и тяжелый, особенно зимой. Да и к тому же мировой экономический кризис отразился даже на Дедах Морозах, поэтому Йоулупукки хочет потратить как можно меньше денег на поездку.

Йоулупукки летает исключительно на санях, запряженных особыми летающими финскими лайками, которых предоставляет единственная авиасобакокомпания FinAirDogLines. На сайте FinAirDogLines Йоулупукки узнал, что в этом сезоне компания осуществляет M двухсторонних рейсов между N городами Европы. При этом резиденция Йоулупукки, гора Корватунтури, имеет номер 1, а международный аэрособакопорт Харькова – номер N.

Рейс номер i соединяет между собой города Ai и Bi и выполняется на санях, запряженных Ci собаками. Одна и та же собака может летать в нескольких рейсах. Стоимость аренды одной собаки составляет 1 евро на любое число рейсов.

Йоулупукки уже не первый год пользуется услугами FinAirDogLines и авиасобакокомпания согласна оплатить ему любые K перелетов, предоставляя своих собак абсолютно бесплатно, но только для этих K перелетов. Собак для остальных рейсов Йоулупукки должен арендовать.

К сожалению, Йоулупукки отличается сильной неторопливостью, присущей всем финнам, поэтому он точно не успеет за неделю вычислить количество собак, которых ему нужно арендовать для поездки из своей резиденции в Харьков. Помогите ему в этих подсчетах.

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


Первая строка входного файла содержит 3 целых числа N, M и K (2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ K < N). Каждая из следующих M строк описывает один двухсторонний рейс и содержит 3 целых числа Ai, Bi, Ci (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi, 1 ≤ Ci ≤ 109). Никакая пара чисел (Ai, Bi) не встречается более одного раза.

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


В выходной файл выведите единственное число – минимальное количество собак, которое должен арендовать Йоулупукки, чтобы добраться из своей резиденции в Харьков. Если Йоулупукки не сможет добраться до Харькова, выведите «-1» (без кавычек).

Пример


joulu.in joulu.out Примечание 
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
 
4
 Йоулупукки следует добираться по маршруту 1–>3–>2–>5, при этом авиасобакокомпания бесплатно предоставляет полет между городами 2 и 5.