Вася очень хочет попасть на сборы в СУНЦ и, к счастью, живет недалеко от него. Поэтому он решил дойти до места проведения сборов пешком. Васе известен план города - какие перекрестки соединены улицами и сколько времени требуется, чтобы пройти по каждой улице. Движение по любой улице разрешено в обе стороны.
Администрация города, однако, решила устроить в этот день уборку улиц от снега. Если на какой-то из улиц происходит уборка, то движение по ней замедляется в два раза. В распоряжении города есть K снегоуборочных машин.
Вася хочет добраться до места назначения как можно быстрее, однако у главы администрации есть с Васей старые счеты, поэтому он хочет максимально замедлить его движение. В результате всякий раз, когда Вася оказывается на перекрестке, глава администрации выбирает не более K улиц, на которых будет производиться уборка, пока Вася перемещается с текущего перекрестка до следующего.
Дом Васи находится около перекрестка с номером 1, а СУНЦ - около перекрестка с номером N. Таким образом, перемещение Васи от дома до СУНЦа выглядит следующим образом. В начале глава выбирает дороги, на которых будет проводиться уборка, затем Вася выбирает улицу, по которой он пойдет от перекрестка 1 (Вася достаточно наблюдателен, чтобы заметить, на каких улицах идет уборка). Когда он доходит до конца выбранной улицы и оказывается на перекрестке, процесс повторяется: глава вновь выбирает улицы для уборки, и машины туда мгновенно перемещаются, а затем Вася - улицу, по которой идти, и т. д. Процесс продолжается, пока Вася не попадет в СУНЦ.
Ваша задача - выяснить, за какое минимально возможное время Васе удастся достичь СУНЦа при условии, что глава администрации всегда действует оптимально.
Входные данные
Первая строка содержит числа N - количество перекрестков в городе, M - количество улиц и K - количество снегоуборочных машин (1 <= N <= 100, 0 <= K <= M <= 20000). Следующие M строк содержат описания улиц в следующем формате: a и b - номера перекрестков, которые данная улица соединяет, t - время движения по данной улице (целое положительное число, не превосходящее 1000).
Выходные данные
Выведите одно число - минимальное время, за которое Вася может добраться до СУНЦа. или -1, если добраться туда невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
1 2 3
1 3 5
2 3 1
|
8
|